June 16, 2024

Big-O Notation: Analyzing Algorithm Efficiency

Asymptotic Analysis

Asymptotic analysis is crucial for understanding and comparing the efficiency of algorithms, especially when dealing with large datasets. Instead of measuring the exact execution time, this analysis focuses on how time (or another resource like space) increases as the input size grows.

Example Code:

public class Program
{
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int sum = SumNumbers(arr);
        Console.WriteLine("Sum: " + sum); // Output: Sum: 15
    }

    public static int SumNumbers(int[] arr)
    {
        int sum = 0; // 1 operation
        for (int i = 0; i < arr.Length; i++) // arr.Length (n) executes n times
        {
            sum += arr[i]; // 1 operation
        }
        
        return sum; // 1 operation
    }
}

In the example of summing the elements of an array, the number of operations is approximately 2 + n, where n is the size of the array. In asymptotic analysis, the term that grows the fastest defines the algorithm's complexity.

Since the dominant term is n, the algorithm's asymptotic complexity is O(n). This indicates a linear growth in execution time as the array size increases.

For example:

  • For n = 100, the execution time is approximately 102.
  • For n = 1.000.000, the execution time is approximately 1.000.002.
  • For n = 1.000.000.000, the execution time is approximately 1.000.000.002.

O(1) - Constant

The Big O(1) describes constant complexity in algorithms. This means that the execution time or the space used by the algorithm remains unchanged, regardless of the size of the input. In other words, if you have an array with 10,000 positions and want to access position 0, the time required for this operation will always be the same, no matter how large the array is

Example Code:

public class Program
{
    public static void Main(string[] args)
    {
        int[] arr = {1, 2, 3, 4, 5};
        int firstElement = getFirstElement(arr);
        Console.WriteLine("First element of the array: " + firstElement); // Output: First element of the array: 1
    }
    
    public static int getFirstElement(int[] arr) {
        return arr[0]; // Returns the first element of the array
    }
}

Graph of this code looks like this:

O(N²) - Quadratic

The Big O(N²) describes quadratic complexity, where the execution time increases proportionally to the square of the input size. This means that as the input size grows, the execution time increases rapidly in an exponential manner, influenced by the square of the input size.

A practical example of this complexity can be found in the solution to the LeetCode challenge problem two-sum.

public class Program
{
    static void Main(string[] args)
    {
        int[] nums = {3, 2, 3};
        var result = TwoSum(nums, 6); // Output: [0, 2]

        foreach (int x in result)
        {
            Console.WriteLine(x);
        }
    }

    static public int[] TwoSum(int[] nums, int target)
    {
        for(int i = 0; i < nums.Length; i++)
        {
            for(int j = i + 1; j < nums.Length; j++)
            {
                if ((nums[i] + nums[j]) == target)
                {
                    return new int[] {i, j};
                }
            }
        }

        return new int[] {};
    }
}

Algorithm Details:

  • Iteration of Loops: The outer loop (for i) iterates over each element in the nums array. The inner loop (for j) iterates over the remaining elements in the array starting after index i.
  • Time Complexity: In the worst case scenario, where no pair of elements satisfies the condition (nums[i] + nums[j]) == target until j reaches the end of the array, each element is compared with all subsequent elements. This results in a total number of operations proportional to N², where N is the number of elements in nums.

Graph of this code looks like this:

O(log n) - Logarithmic

The Big O(log n) complexity describes algorithms where the execution time increases logarithmically with the size of the input. In other words, as the input size (n) increases, the execution time increases proportionally to the logarithm of that size. This results in much slower growth compared to linear O(n) or quadratic O(n²) complexity algorithms.

Example Code:
Binary search is a classic example of an algorithm with O(log n) complexity. This algorithm is used to find an element in a sorted array by repeatedly dividing the search space in half.

public class Program
{
    public static void Main()
    {
        int[] array = { 2, 3, 5, 7, 9, 11, 13, 17, 19, 23 };
        int target = 11;

        int index = BinarySearch(array, target);

        Console.WriteLine(index); // Output: 5
    }

    public static int BinarySearch(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (array[mid] == target)
                return mid;

            if (array[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1;
    }
}

How Binary Search Works:

  • Halving the Search Space: Binary search repeatedly halves the search space. In each iteration, the algorithm checks the middle element of the array (index mid) and decides whether the target is in the left half or the right half.

  • Time Efficiency: Thanks to its halving strategy, binary search operates in O(log n) in the worst case. This means that even for a large number of elements, the number of operations required to find the target increases much slower than the number of elements in the array.

Graph of this code looks like this:

O(n log n) - Linear Logarithmic Complexity

The Big O(n log n) describes algorithms whose execution time increases linearly relative to the input size, but logarithmically. This type of complexity is common in efficient sorting algorithms and divide-and-conquer techniques.


Explanation:

The O(n log n) complexity often appears when an algorithm repeatedly divides the problem into smaller parts, processes each part independently, and then combines the solutions. The term log n arises because the problem is divided logarithmically into smaller parts.


Code Example:

Here's an example of implementing Merge Sort in C#. This algorithm demonstrates O(n log n) complexity by dividing the list into smaller parts, sorting them individually, and then merging them back in order.

public class Program
{
    public static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6, 7 };

        MergeSort(arr, 0, arr.Length - 1);

        PrintArray(arr); // Output: [5, 6, 7, 11, 12, 13]
    }

    public static void MergeSort(int[] arr, int left, int right)
    {
        if (left < right)
        {
            int mid = left + (right - left) / 2;

            MergeSort(arr, left, mid);
            MergeSort(arr, mid + 1, right);

            Merge(arr, left, mid, right);
        }
    }

    public static void Merge(int[] arr, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        int iL = 0, iR = 0;
        int k = left;
        while (iL < n1 && iR < n2)
        {
            if (L[iL] <= R[iR])
            {
                arr[k] = L[iL];
                iL++;
            }
            else
            {
                arr[k] = R[iR];
                iR++;
            }
            k++;
        }

        while (iL < n1)
        {
            arr[k] = L[iL];
            iL++;
            k++;
        }

        while (iR < n2)
        {
            arr[k] = R[iR];
            iR++;
            k++;
        }
    }

    public static void PrintArray(int[] arr)
    {
        foreach (var num in arr)
        {
            Console.Write(num + " ");
        }
        
        Console.WriteLine();
    }
}

How Merge Sort Works:

  1. Divide: The MergeSort function divides the array into two halves until each subarray has only one element.
  2. Sort: Each subarray is individually sorted.
  3. Merge: The sorted subarrays are efficiently merged to produce the final sorted array.

Time Efficiency:

  • Division (MergeSort): O(n log n) - due to recursion dividing the array logarithmically.
  • Combination (Merge): O(n) - due to the linear process of merging subarrays.

The graph of this code looks like this:

O(2^n) - Exponential Complexity

The O(2^n) complexity describes algorithms whose execution time grows exponentially with the increase in input size. Each increment in input size results in a doubling of the execution time. Algorithms with this complexity quickly become impractical for large inputs.

Example in C#: Recursive Fibonacci

The recursive implementation of the Fibonacci sequence is a classic example of an algorithm with exponential complexity.

public class Program
{
    public static void Main()
    {
        int n = 10;
        var result = Fibonacci(n);
        Console.WriteLine(result); // Output: 55
    }

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

Explanation:

  1. Base Cases: If n is 0 or 1, it returns n.
  2. Recursion: For n > 1, the function calls itself for n-1 and n-2.
  3. Exponential Growth: The number of recursive calls grows exponentially.

This implementation is simple but inefficient for large values of n due to the rapid growth in the number of operations.

The graph of this code looks like:

O(n!) - Factorial Complexity

The Big O(n!) complexity describes algorithms whose runtime grows according to the factorial of the input size. This growth is extremely rapid and makes algorithms impractical for large inputs. It is common in problems that involve generating all possible permutations of a set.

Example Code:

Let's see a simpler example in C# to generate all permutations of a string. This example illustrates factorial complexity clearly and concisely.

public class Program
{
    public static void Main()
    {
        string str = "ABC";
        Permute(str, 0, str.Length - 1); // Output: All permutations of "ABC" are: ABC, ACB, BAC, BCA, CBA, CAB
    }

    public static void Permute(string str, int l, int r)
    {
        if (l == r)
            Console.WriteLine(str);
        else
        {
            for (int i = l; i <= r; i++)
            {
                str = Swap(str, l, i);
                Permute(str, l + 1, r);
                str = Swap(str, l, i);
            }
        }
    }

    public static string Swap(string str, int i, int j)
    {
        char[] charArray = str.ToCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return new string(charArray);
    }
}

How the permutation algorithm works:

  • Swap: Swaps characters at positions i and j of the string.
  • Recursion: Calls the Permute function recursively to generate permutations of the remaining characters.
  • Backtracking: Reverts the swap to explore other permutations.

Time Efficiency:

  • Factorial Growth: O(n!) - each increment in n results in factorial growth in the number of operations.

Performance:

  • For small inputs, the permutation algorithm works well. However, for larger inputs, the number of permutations grows extremely fast, making the execution time impractical.

The graph of this code looks like:

Conclusion

Asymptotic analysis, using Big-O notation, is essential for understanding and comparing the efficiency of algorithms, especially when dealing with large datasets. Instead of focusing on the exact execution time, this analysis evaluates how time or the use of other resources increases as the size of the input grows.

Below, we summarize the main complexities discussed:

  1. O(1) - Constant: Execution time does not depend on the size of the input. Example: accessing a specific element in an array.
  2. O(n) - Linear: Execution time grows linearly with the size of the input. Example: summing all elements of an array.
  3. O(n²) - Quadratic: Execution time grows proportionally to the square of the size of the input. Example: two-sum problem.
  4. O(log n) - Logarithmic: Execution time grows logarithmically with the size of the input. Example: binary search in a sorted array.
  5. O(n log n) - Linear Logarithmic: Execution time grows linearly relative to the size of the input, but logarithmically. Example: Merge Sort algorithm.
  6. O(2^n) - Exponential: Execution time grows exponentially with increasing input size. Example: recursive calculation of the Fibonacci sequence.
  7. O(n!) - Factorial: Execution time grows according to the factorial of the input size. Example: generating all permutations of a string.

Each of these examples illustrates how asymptotic analysis helps predict the behavior of an algorithm as the input size increases, enabling developers and software engineers to make informed choices about which algorithms to use in different scenarios. Understanding these complexities is crucial for designing and implementing efficient and scalable systems.