Decoding the Order of Growth in Programs

Introduction

When analyzing the performance of algorithms, we often consider their order of growth or how their performance scales as the input size increases. In C#, we can use Big O notation to describe the order of growth of algorithms. Big O notation provides an upper bound on the growth rate of an algorithm’s running time in terms of the input size.
Here are some common orders of growth, ordered from best to worst:

O(1): constant time – The running time does not depend on the input size. Examples include accessing an array element by index or performing a single arithmetic operation.
O(log n): logarithmic time – The running time increases slowly as the input size grows. Examples include binary search on a sorted array or searching a balanced binary search tree.
O(n): linear time – The running time increases proportionally to the input size. Examples include iterating through an array or linked list.
O(n log n): linearithmic time – The running time increases faster than linear time but slower than quadratic time. Examples include merge sort and quicksort.
O(n^2): quadratic time – The running time grows exponentially with the input size. Examples include bubble sort and selection sort.
O(2^n): exponential time – The running time grows extremely fast with the input size. Examples include brute force algorithms that try every possible combination of inputs.

Pioneers in Cloud Consulting & Migration Services

Reduced infrastructural costs
Accelerated application deployment

Get Started

Examples of How to Analyze the Order of Growth of Algorithms in C#

Iterating through an array

Consider the following code that iterates through an array of size n and performs a constant-time operation on each element:

int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
    Console.WriteLine(arr[i]);
}

int[] arr = new int[n];

for (int i = 0; i < n; i++)

{

Console.WriteLine(arr[i]);

}

Binary search

Consider the following code that performs a binary search on a sorted array of size n:

int BinarySearch(int[] arr, int key)
{
    int low = 0;
    int high = arr.Length - 1;
 
    while (low <= high)
    {
        int mid = (low + high) / 2;
 
        if (arr[mid] == key)
        {
            return mid;
        }
        else if (arr[mid] < key)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

int BinarySearch(int[] arr, int key)

{

int low = 0;

int high = arr.Length - 1;

while (low <= high)

{

int mid = (low + high) / 2;

if (arr[mid] == key)

{

return mid;

}

else if (arr[mid] < key)

{

low = mid + 1;

}

else

{

high = mid - 1;

}

return -1;

}

Since each, while loop iteration halves the search space, the running time is O(log n).

Bubble sort

Consider the following code that performs bubble sort on an array of size n:

void BubbleSort(int[] arr)
{
    int n = arr.Length;
 
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

void BubbleSort(int[] arr)

{

int n = arr.Length;

for (int i = 0; i < n - 1; i++)

{

for (int j = 0; j < n - i - 1; j++)

{

if (arr[j] > arr[j + 1])

{

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

Quick sort

Consider the following code that performs a quick sort on an array of size n:

void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {

        int pivotIndex = Partition(arr, left, right);
        QuickSort(arr, left, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, right);
    }
}
 
int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;
 
    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
 
    int temp2 = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp2;
 
    return i + 1;
}

void QuickSort(int[] arr, int left, int right)

{

if (left < right)

{

int pivotIndex = Partition(arr, left, right);

QuickSort(arr, left, pivotIndex - 1);

QuickSort(arr, pivotIndex + 1, right);

}

int Partition(int[] arr, int left, int right)

{

int pivot = arr[right];

int i = left - 1;

for (int j = left; j < right; j++)

{

if (arr[j] < pivot)

{

i++;

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

int temp2 = arr[i + 1];

arr[i + 1] = arr[right];

arr[right] = temp2;

return i + 1;

}

Conclusion

The partition function partitions the array into two parts, with all elements less than the pivot on the left and all elements greater than the pivot on the right. The Quicksort function recursively calls itself on the left and right partitions.

Since the partition function takes linear time and is called recursively log n times, the running time is O(n log n). In conclusion, when analyzing the performance of algorithms in C#, it is important to consider their order of growth. Big O notation provides a useful way to describe the upper bound on the growth rate of an algorithm’s running time in terms of the input size. We can choose the most efficient algorithm for a given problem by understanding the order of growth of different algorithms.

Making IT Networks Enterprise-ready – Cloud Management Services

Accelerated cloud migration
End-to-end view of the cloud environment

Get Started

About CloudThat

CloudThat is an award-winning company and the first in India to offer cloud training and consulting services worldwide. As a Microsoft Solutions Partner, AWS Advanced Tier Training Partner, and Google Cloud Platform Partner, CloudThat has empowered over 850,000 professionals through 600+ cloud certifications winning global recognition for its training excellence including 20 MCT Trainers in Microsoft’s Global Top 100 and an impressive 12 awards in the last 8 years. CloudThat specializes in Cloud Migration, Data Platforms, DevOps, IoT, and cutting-edge technologies like Gen AI & AI/ML. It has delivered over 500 consulting projects for 250+ organizations in 30+ countries as it continues to empower professionals and enterprises to thrive in the digital-first world.

FAQs

1. What is an algorithm's growth order in C#?

ANS: – The order of growth of an algorithm in C# refers to the computational complexity or the rate at which the algorithm’s performance (time or space) scales with the input size. It is commonly expressed using Big O notation, which provides an upper bound on the growth rate. For example, an algorithm with a time complexity of O(n) means that the algorithm’s running time grows linearly with the input size.

2. Can the order of growth of an algorithm be different in C# compared to other programming languages?

ANS: – An algorithm’s growth order is determined by its fundamental characteristics and logic rather than the programming language. Therefore, the order of growth remains the same across different programming languages. However, the actual running times of algorithms can vary due to language-specific optimizations and hardware differences.