Big O Notation

Big O Notation is a mathematical notation that describes the efficiency of an algorithm. This is useful to evaluate the efficiency of an algorithm, independently of the hardware that is executing it. In this article, I explain about it, using code examples in .NET.

The Big O notation is represented by O(n) and it is used to classify algorithms according to how their runtime and space requirements grow as the input size grows. This notation represents the cost or processing time (time complexity) for the worst-case scenario for an algorithm, and the n represents the input size. In summary, it is a way to specify how efficient an algorithm is as the size of the input data grows.

Big O uses the letter O followed by a function in parentheses, like O(n) or O(n²), etc. The function inside the parentheses, like n (input size), tells you how the algorithm’s time or space complexity grows with the input size.

These are the most common representations:

1. O(1) — Constant time complexity: algorithms whose runtime does not depend on the size of the input. There are no changes in the number of operations, as it does not depend on the input size (n). For these algorithms, the execution time remains constant regardless of the input size.
2. O(log n) — Logarithmic time complexity: algorithms whose runtime grows logarithmically with the size of the input. The growth of operations number is lower than the number of items.
3. O(n) — Linear time complexity: algorithms whose runtime grows linearly with the size of the input. The growth of the operations number is proportional to the growth of the items number.
4. O(n log n) — Linearithmic Time Complexity: algorithms whose runtime grows in proportion to n times the logarithm of n. It is the result of log n operations, executed n times.
5. O(n²) or O (n^2) — Quadratic time complexity: algorithms whose runtime grows quadratically with the size of the input. This occurs when the items are processed in pairs, many times with repetitions inside a repetition, for example, a for inside another for.
6. O(2^n) — Exponential time complexity: algorithms whose runtime grows exponentially with the size of the input. As n grows, the time and space grow exponentially.
7. O(n!) — Factorial time complexity: algorithms whose runtime increases factorially with the size of the input. The number of executed instructions grows very fast for a small number of data.

Below you can see the Big-O Complexity Chart:

source: https://www.bigocheatsheet.com/

In this chart, the O(1) is the more performatic, and the O(n!) is the worst. These are the representation of each notation:

• O(1) — Excellent, the best.
• O(log n) — Good.
• O(n) — Fair.
• O(n log n) — Bad.
• O(n^2)/O(n²), O(2^n) and O(n!) — Horrible, the worst.

For demonstration purposes, I created a console application using .NET. The complete code can be found on my GitHub. Most of the algorithms presented in this article are well-known algorithm that can be easily found on the internet.

O(1) — Constant Time Complexity

O(1) represents the best-case scenario in terms of efficiency. Algorithms that have O(1) time complexity mean that the time taken to perform the operation does not depend on the size of the input data. Regardless of the input size, the time complexity remains constant, making these operations highly efficient.

These are some examples of algorithms that have an O(1) notation:

• Accessing an element in an array by searching by the index: regardless of the size of the array, as we are searching by its index, it will take a constant time.
• Checking if a number is even or odd: no matter which is the number the cost of this algorithm is always the same.

Here is an example of an O(1) algorithm:

public static int GetArrayValueByIndex(int[] array, int index)
{
    return array[];
}

Regardless of the size of the array, accessing a specific element by its index takes constant time.

O(1) algorithms means that the algorithm’s speed remains unaffected by the data volume it handles. This is particularly desirable for performance-critical applications.

O(log n) — Logarithmic Time Complexity

Algorithms that have O(log n) time complexity are algorithms whose execution time grows logarithmically in proportion to the size of the input data, represented by n. This means that as the input size increases, the time taken by the algorithm to complete its operation increases at a logarithmic rate.

A logarithmic rate means that the execution time of the algorithm does not increase at the same rate as the input size. Instead, it increases more slowly, following a logarithm function. This means that as the input size gets bigger (i.e. doubles or triples), the algorithm’s runtime increases by only a limited amount. In summary, a logarithmic rate means that the algorithm’s runtime grows more slowly than the input size, which is a desirable characteristic in terms of algorithm efficiency.

These are some examples of algorithms that have an O(log n) notation:

• Binary Search: in a sorted array of size n, binary search repeatedly divides the search interval in half. This results in a time complexity of O(log n) because the search space is halved in each step.
• Finding the Height of a Balanced Binary Tree: In a balanced binary tree with n nodes, the height of the tree is logarithmic with respect to the number of nodes. This is because at each level, the number of nodes approximately doubles, resulting in a height of O(log n).

Here is an example of an O(log n) algorithm:

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

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

       // Check if target is present at mid
       if (arr[mid] == target)
       {
           return mid;
       }

       // If target greater, ignore left half
       if (arr[mid] < target)
       {
           left = mid + 1;
       }
       else // If target is smaller, ignore right half
       {
           right = mid - 1;
       }
   }

   // Return -1 if element was not present
   return -1;
}

Consider this binary search algorithm. If you double the size of the input data set, the number of operations required to find an item increases only by a logarithmic factor, which is significantly less than doubling. This is because the binary search algorithm efficiently halves the data set with each step, reducing the number of operations required as the data set grows. So this algorithm has a time complexity of O(log n) because it halves the search space in each iteration of the while loop.

O(n) — Linear Time Complexity

Algorithms that have O(n) time complexity are algorithms that the runtime grow linearly with the size of the input (n). This means that if the size of the input doubles, the runtime of the algorithm also doubles, for example, think about iterating over a list, where the larger the list size, the greater the processing.

These are some examples of algorithms that have an O(n) notation:

• Iterating over arrays or lists: where each element in the input is processed once. In the worst-case scenario, the algorithm needs to traverse the entire array. A simple loop fits into this category.
• Finding the maximum element in an unsorted array by iterating over each element once.
• Linear search algorithm: which traverses the entire array or list sequentially to find a target element. In the worst-case scenario, the target element may be the last element in the array, or it may not be present at all, requiring the algorithm to iterate through all elements.

Here is an example of an O(n) algorithm:

public static int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
            return i;
    }

    return -1;
}

Consider this Linear Search algorithm, which iterates through each element of an array once to find a specific value. As the size of the array increases, the algorithm will take proportionally more time to search through each element until it finds the desired value.

Linear time complexity implies that the algorithm’s performance will degrade linearly as the input size grows. However, algorithms with linear time complexity are generally considered efficient for moderate-sized inputs, and they can often scale well to larger inputs compared to algorithms with higher time complexities.

O(n log n) — Linearithmic Time Complexity

Algorithms that have O(n log n) time complexity are algorithms that the growth rate of the algorithm’s performance remains relatively consistent as the input size increases. It describes algorithms whose runtime increases in proportion to the size of the input (n).

They are algorithms whose performance grows moderately as the input size increases, with the logarithmic factor ensuring a balanced and efficient execution across various scenarios. In simple terms, it is log n executed n times.

These are some examples of algorithms that have an O(n log n) notation:

• Merge Sort: this is a divide-and-conquer algorithm that recursively divides the array into two halves until each subarray contains only one element, and then, it merges the subarrays in a sorted manner. Since the array is divided recursively log n times, and each merge operation takes linear time, the overall time complexity of Merge Sort is O(n log n).
• Heap Sort: this is a comparison-based sorting algorithm, it builds a max-heap from the input array and repeatedly extracts the maximum element from the heap, resulting in a sorted array. Since the array is divided recursively log n times, and each merge operation takes linear time, the overall time complexity of Merge Sort is O(n log n).

Here is an example of O(n log n) algorithm:

public static class ONLogN
{
   public static void MergeSort(int[] array)
   {
       if (array.Length <= 1)
           return;

       int mid = array.Length / 2;
       int[] leftArray = new int[mid];
       int[] rightArray = new int[array.Length - mid];

       // Copy elements to left and right arrays
       Array.Copy(array, 0, leftArray, 0, mid);
       Array.Copy(array, mid, rightArray, 0, array.Length - mid);

       // Recursively sort left and right arrays
       MergeSort(leftArray);
       MergeSort(rightArray);

       // Merge sorted arrays
       int leftIndex = 0, rightIndex = 0, resultIndex = 0;

       // Compare elements from left and right arrays and merge them into result array
       while (leftIndex < leftArray.Length && rightIndex < rightArray.Length)
       {
           if (leftArray[leftIndex] <= rightArray[rightIndex])
               array[resultIndex++] = leftArray[leftIndex++];
           else
               array[resultIndex++] = rightArray[rightIndex++];
       }

       // Copy remaining elements from left array, if any
       while (leftIndex < leftArray.Length)
           array[resultIndex++] = leftArray[leftIndex++];

       // Copy remaining elements from right array, if any
       while (rightIndex < rightArray.Length)
           array[resultIndex++] = rightArray[rightIndex++];
   }
}

Consider the Merge Sort algorithm, the input array is repeatedly divided in half until individual elements are reached (logarithmic factor), and then the sorted subarrays are merged together (linear factor). As a result, this algorithm has a time complexity of O(n log n) where n is the size of the input array.

Algorithms with linearithmic time complexity are often efficient for large input sizes and are commonly used in sorting and searching problems.

O(n²) — Quadratic Time Complexity

Algorithms that have O(n²) time complexity are algorithms that the time taken by the algorithm to solve a problem increases quadratically with the size of the input. This time complexity commonly occurs in algorithms where there are nested loops (i.e.: a loop inside another loop), and the number of iterations in each loop depends on the size of the input. As the input size increases, the total number of iterations grows proportional to the square of the input size. In other words, if the size of the input doubles, the runtime of the algorithm approximately quadruples.

For example, consider an algorithm that involves comparing each element of an array with every other element. If the array has n elements, then the number of comparisons required would be on the order of n². In general, any algorithm that involves nested iterations or comparisons of every element with every other element is likely to have O(n²) time complexity.

Attention: Quadratic time complexity can lead to performance issues, especially for large input sizes. Therefore, it’s generally desirable to avoid algorithms with quadratic time complexity when possible and strive for more efficient solutions.

These are some examples of algorithms that have an O(n²) notation:

• Bubble Sort: where each element in the array is compared with every other element, resulting in a total of n² comparisons in the worst case scenario.
• Selection Sort: this divides the input array into two parts: sorted and unsorted, and in each iteration, the algorithm selects the minimum (or maximum) element from the unsorted part and moves it to the sorted part. The selection process involves scanning through the unsorted part of the array, resulting in n² comparisons.
• Insertion Sort: where each element from the unsorted part of the array is sequentially inserted into its correct position in the sorted part. This process requires comparisons and shifting of elements, resulting in quadratic time complexity.

Here is an example of an O(n²) algorithm:

public static 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])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

Consider this Bubble Sort algorithm, in the worst case, Bubble Sort compares each element of the array with every other element, resulting in n * n comparisons, where n is the number of elements in the array. This leads to a total of n² comparisons, making Bubble Sort O(n²) in terms of time complexity.

Algorithms with quadratic time complexity have a runtime that grows quadratically with the size of the input, making them less efficient for large data sets compared to algorithms with lower time complexities like linear O(n) or logarithmic O(log n).

O(2^n) — Exponential Time Complexity

Algorithms that have O(2^n) time complexity are algorithms whose runtime grows exponentially with the size of the input. In other words, as the input size increases, the time taken to execute the algorithm grows at an exponential rate.

Algorithms where the items are processed in pairs, many times with repetitions inside a repetition, for example a loop inside a loop, fit in this notation.

Algorithms with O(2^n) time complexity are highly inefficient and should be avoided for large input sizes whenever possible due to their exponential growth in runtime. The growth rate of exponential time complexity is extremely rapid and becomes infeasible for even moderately large input sizes.

These are some examples of algorithms that have an O(2^n) notation:

• Subset Generation: where each element in the original set can be included or excluded in each subset, resulting in a total of 2^n possible subsets.
• Backtracking Algorithms: Backtracking algorithms, such as those used in Sudoku solvers or certain types of graph traversal problems, explore all possible solutions recursively and backtrack when a dead end is reached. The number of recursive calls and the branching factor at each step can lead to exponential time complexity.
• Recursive algorithm: this kind of algorithm with exponential growth in the number of recursive calls can also exhibit O(2^n) time complexity. For example, the “Towers of Hanoi”

Here is an example of O(2^n) algorithm:

public static List<List<int>> GenerateSubsets(int[] nums)
{
   List<List<int>> result = new List<List<int>>();
   int n = nums.Length;

   // Total number of subsets is 2^n
   for (int i = 0; i < (1 << n); i++)
   {
       List<int> subset = new List<int>();

       // Construct subset based on binary representation of i
       for (int j = 0; j < n; j++)
       {
           if ((i & (1 << j)) > 0)
           {
               subset.Add(nums[j]);
           }
       }

       result.Add(subset);
   }

   return result;
}

Consider this algorithm, as the size of the input array nums increases, the number of subsets generated grows exponentially. The algorithm essentially generates all possible subsets of the input array by considering all possible combinations of including or excluding each element, resulting in a total of 2^n subsets.

O(n!) — Factorial Time Complexity

Algorithms that have O(n!) time complexity are algorithms whose runtime increases factorially with the size of the input, resulting in extremely slow performance for even moderately sized inputs. In this kind of algorithm, each additional element in the input will cause the number of operations required to solve the problem to multiply by the size of the input.

This kind of algorithm is considered very inefficient and impractical for large inputs, as the number of operations required quickly becomes astronomical. Therefore, algorithms with factorial time complexity are typically avoided in favor of more efficient alternatives whenever possible.

These are some examples of algorithms that have an O(n!) notation:

• Permutation Generation: where each element in the original set can be permuted with all remaining elements.
• Brutal force solution for the Traveling Salesman Problem (TSP): this is a classic problem which can be solved by considering all possible permutations of cities to find the shortest tour. The time complexity of such algorithms grows exponentially with the number of elements to be considered.

Here is an example of O(n!) algorithm:

public static void GeneratePermutations(int n, int[] nums, List<List<int>> result)
{
    if (n == 1)
    {
        List<int> permutation = new List<int>(nums);
        result.Add(permutation);
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            GeneratePermutations(n - 1, nums, result);
            if (n % 2 == 0)  // For even 'n', swap nums[i] with nums[n-1]
            {
                Swap(nums, i, n - 1);
            }
            else  // For odd 'n', always swap nums[0] with nums[n-1]
            {
                Swap(nums, 0, n - 1);
            }
        }
    }
}

private static void Swap(int[] nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

This algorithm generates all possible permutations (a rearrangement of the elements of a set into a specific order) of the given array nums. The time complexity of this algorithm is O(n!), where n is the number of elements in the input array. As the size of the array increases, the number of permutations grows factorially, resulting in an exponential increase in the number of recursive calls and overall execution time.

Algorithms with factorial time complexity are extremely inefficient and generally impractical for all but the smallest inputs. They are typically avoided in favor of more efficient algorithms whenever possible.

Benchmark Result

In the image below you can see the benchmark result for these algorithms (the factorial example was not executed in the benchmark, cause it would take too much time):

Here is the complete result table:

| Method                            | Mean                  | Error              | StdDev              | Median                | Rank |
|---------------------------------- |----------------------:|-------------------:|--------------------:|----------------------:|-----:|
| 'O(1) - Get Array value by Index' |             0.3568 ns |          0.0454 ns |           0.0948 ns |             0.3328 ns |    1 |
| 'O(log n) - Binary Search'        |            29.4904 ns |          0.6250 ns |           1.8134 ns |            28.7106 ns |    2 |
| 'O(n) - Linear Search'            |         3,343.8529 ns |         65.8623 ns |         108.2136 ns |         3,365.2576 ns |    3 |
| 'O(n log n) - Merge Sort'         |       412,878.6469 ns |     14,113.2123 ns |      40,036.8341 ns |       409,503.3691 ns |    4 |
| 'O(n^2) - Bubble Sort'            |    56,810,744.5000 ns |  1,803,596.4298 ns |   5,317,944.7666 ns |    56,206,856.2500 ns |    5 |
| 'O(2^n) - Generate Subsets'       | 1,278,584,435.0000 ns | 53,516,114.1767 ns | 157,793,470.0977 ns | 1,196,049,200.0000 ns |    6 |

Conclusion

Big O notation is a way to analyze the efficiency of algorithms and understand how their performance scales with the size of the input. By providing a standardized way to express algorithmic complexity, Big O notation helps developers compare algorithms and choose the most efficient approach when designing and implementing algorithms. It also allows us to reason about the efficiency of algorithms and ultimately write more efficient and scalable code.

This is the link for the project in GitHub: https://github.com/henriquesd/BigONotationDemo

If you like this demo, I kindly ask you to give a ⭐️ in the repository.

Thanks for reading!

References

Big-O Cheat Sheet