Bid O Notation And Few Examples

Time complexity is commonly estimated by counting the number of elementary operations, performed in the algorithm. When we refer to the elementary operation we refer to the operation that takes a fixed amount of time to preform. This is where the Big O Notation comes to place.

What is the 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. 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:

• 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.
• 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.
• 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.
• O(n log n) — Linear 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.
• 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.
• 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.
• O(n!) — Factorial time complexity: algorithms whose runtime increases factorial 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: Big O Cheat Sheet

In the Big O Cheat Sheet you can try to find how your algorithm classify, like as a "merge-sort" or a "quick-sort". Whenever you’re coding loops within loops, you want to be especially mindful of time complexity.

Examples

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.

• 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)
{
    // Directly return the value at the specified index
    return array[index];
}

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.

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.

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

public static int BinarySearch(int[] arr, int target)
{
    // Initialize two pointers, one at the start of the array and one at the end
    int left = 0;
    int right = arr.Length - 1;

    // Continue searching as long as the left pointer is less than or equal to the right pointer
    while (left <= right)
    {
        // Calculate the middle index
        int mid = left + (right - left) / 2;

        // If the target is found at the middle index, return its index
        if (arr[mid] == target)
        {
            return mid;
        }

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

    // If the target is not found in the array, return -1
    return -1;
}

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.

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

public static int LinearSearch(int[] arr, int target)
{
    // Iterate through each element in the array
    for (int i = 0; i < arr.Length; i++)
    {
        // If the current element matches the target, return its index
        if (arr[i] == target)
            return i;
    }

    // If the target is not found in the array, return -1
    return -1;
}

Linear time complexity implies that the algorithm’s performance will degrade linearly as the input size grows.

In the upcoming article, we are going to take a look at the exponential time complexity and quadratic time complexity, which happens to be the complexity of the bubble sort. Each element in the array is compared with every other element.

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.