Development

Understanding Big O Notation

7 months ago

Big O Notation is a mathematical concept used in computer science to describe the efficiency of algorithms in terms of their time and space complexity. It helps developers understand how an algorithm’s runtime or memory usage grows as the size of the input increases. In this article, we’ll explore the most common Big O notations with examples in C#.

What is Big O Notation?

Big O notation classifies algorithms according to their worst-case or average-case performance. It’s primarily used to analyze the time complexity (execution time) and space complexity (memory usage) of algorithms as the input size grows. Let’s dive into some common Big O notations with examples in C#.

Common Big O Notations

  1. O(1) – Constant Time Complexity
  2. O(log n) – Logarithmic Time Complexity
  3. O(n) – Linear Time Complexity
  4. O(n log n) – Linearithmic Time Complexity
  5. O(n^2) – Quadratic Time Complexity
  6. O(2^n) – Exponential Time Complexity

1. O(1) – Constant Time Complexity

An algorithm with O(1) complexity has a constant runtime regardless of the input size. It’s the most efficient in terms of time because it doesn’t change with n.

Example: Accessing an element in an array

C#
int[] array = { 10, 20, 30, 40, 50 };
int value = array[2]; // Accessing an element by index takes constant time.
Console.WriteLine(value); // Output: 30

In this example, accessing an element by index in an array is always done in constant time, O(1), because we go directly to the element’s memory location.

2. O(log n) – Logarithmic Time Complexity

An algorithm with O(log n) complexity reduces the problem size by a certain factor each time, often found in algorithms that divide the input in half with each iteration, like binary search.

Example: Binary Search

C#
int BinarySearch(int[] sortedArray, int target)
{
    int left = 0;
    int right = sortedArray.Length - 1;
    
    while (left <= right)
    {
        int middle = left + (right - left) / 2;
        
        if (sortedArray[middle] == target)
            return middle;
        
        if (sortedArray[middle] < target)
            left = middle + 1;
        else
            right = middle - 1;
    }
    
    return -1; // Not found
}

// Usage
int[] sortedArray = { 1, 3, 5, 7, 9, 11 };
int targetIndex = BinarySearch(sortedArray, 7);
Console.WriteLine(targetIndex); // Output: 3

Binary search has a time complexity of O(log n) because it divides the search interval in half each time.

3. O(n) – Linear Time Complexity

An algorithm with O(n) complexity grows linearly with the input size, meaning the runtime increases in direct proportion to n.

Example: Linear Search

C#
int LinearSearch(int[] array, int target)
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i] == target)
            return i;
    }
    
    return -1; // Not found
}

// Usage
int[] array = { 4, 2, 7, 1, 3 };
int targetIndex = LinearSearch(array, 7);
Console.WriteLine(targetIndex); // Output: 2

4. O(n log n) – Linearithmic Time Complexity

Algorithms with O(n log n) complexity typically involve sorting. The merge sort and quick sort algorithms fall into this category.

Example: Merge Sort

C#
void MergeSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        MergeSort(array, left, middle);
        MergeSort(array, middle + 1, right);
        Merge(array, left, middle, right);
    }
}

void Merge(int[] array, int left, int middle, int right)
{
    int leftSize = middle - left + 1;
    int rightSize = right - middle;
    
    int[] leftArray = new int[leftSize];
    int[] rightArray = new int[rightSize];
    
    Array.Copy(array, left, leftArray, 0, leftSize);
    Array.Copy(array, middle + 1, rightArray, 0, rightSize);
    
    int i = 0, j = 0, k = left;
    while (i < leftSize && j < rightSize)
    {
        if (leftArray[i] <= rightArray[j])
        {
            array[k] = leftArray[i];
            i++;
        }
        else
        {
            array[k] = rightArray[j];
            j++;
        }
        k++;
    }
    
    while (i < leftSize)
    {
        array[k] = leftArray[i];
        i++;
        k++;
    }
    
    while (j < rightSize)
    {
        array[k] = rightArray[j];
        j++;
        k++;
    }
}

// Usage
int[] array = { 38, 27, 43, 3, 9, 82, 10 };
MergeSort(array, 0, array.Length - 1);
Console.WriteLine(string.Join(", ", array)); // Output: 3, 9, 10, 27, 38, 43, 82

Merge sort has O(n log n) complexity due to the need to divide the array and merge each half.

5. O(n^2) – Quadratic Time Complexity

An algorithm with O(n^2) complexity involves nested loops where each element is compared to every other element. The runtime grows quadratically as n increases, making it inefficient for large inputs.

Example: Bubble Sort

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

// Usage
int[] array = { 5, 3, 8, 4, 2 };
BubbleSort(array);
Console.WriteLine(string.Join(", ", array)); // Output: 2, 3, 4, 5, 8

Bubble sort has O(n^2) complexity because it requires two nested loops to compare and swap elements.

6. O(2^n) – Exponential Time Complexity

Algorithms with O(2^n) complexity are highly inefficient for large n values, as the runtime doubles with each increment of n. This complexity often appears in recursive solutions to problems like the Fibonacci sequence.

Example: Fibonacci Sequence (Recursive)

C#
int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

// Usage
int result = Fibonacci(5);
Console.WriteLine(result); // Output: 5 (0, 1, 1, 2, 3, 5)
Tags:
Shares: