Data Structures and Algorithm: The Big O Notation for Time Complexity

Big O (O) is one of the three mathematical notations used to describe the asymptotic behavior of algorithms. Asymptotic behavior refers to a function's performance as its input size grows indefinitely.

Big O describes the worst-case scenario or upper bound for an algorithm's growth rate. For example, for a linear search in an array, the worst-case scenario is that the value is the last element or isn’t present at all, requiring you to loop through the entire array.

The other two notations are Big Omega (which represents the best-case scenario) and Big Theta (which applies when both the best-case and worst-case scenarios fall within the same growth rate as input size increases).

Understanding the worst-case scenario through Big O helps us anticipate the maximum performance impact of an algorithm when things go wrong, allowing us to take steps to ensure your programs don’t crash or become inefficient.

Why is this important?

A great way to see the importance of algorithm performance is by comparing linear search and binary search. Let’s use an example from Grokking Algorithms. Imagine Bob needs to write a search algorithm for NASA to find a rocket landing spot. The rocket has only ten seconds to land on the correct spot—any delay could cause it to go off course.

Bob first considers a simple linear search, which can be written quickly with few bugs. This algorithm checks each potential landing spot one by one. It's straightforward, but at what cost?

Bob tests out his linear search algorithm with 100 elements, and it takes 100ms to find the correct spot. However, using binary search, Bib sees it can search through the same 100 elements in just 7ms (log? 100 ≈ 7). Based on this, he estimates that binary search is about 15 times faster than linear search (100ms / 7ms).

Using just the binary search, Bob tests out a larger data set of 1 billion. He finds his spot in 32 ms. So if the binary search is 15 times faster, he believes the linear search will take around 450 ms (32ms * 15).

His thoughts are wrong. Very wrong.

The time complexity of linear search grows proportionally to the number of elements, hence the name. So if 100 elements took 100 ms, searching through 1 billion elements would take 1 billion ms (or roughly 11.5 days)!

The runtime of different algorithms grows at different rates. Binary search grows logarithmically, which results in significantly faster performance for large data sets. It's not enough to simply know how long an algorithm takes for one input size—you need to understand how its running time increases as the input grows, which is exactly what Big O notation helps us with.

How to Determine the Big O Notation for an Algorithm

Worst Case Scenario

When calculating Big O, always consider the worst-case scenario. For example, if you’re searching for "Nemo" in an array of names, the worst case would be that "Nemo" is the last name on the list. In this case, your loop will run n times, where n is the total number of names in the array. In Big O terms, this is expressed as O(n), which is read as "O of n."

Remove Constants

Some operations in your code are constant, such as assignments. When calculating Big O, you ignore constants because they become insignificant as the input size grows. If your algorithm runs in n + 3 steps, the constant 3 becomes negligible as n increases. So, you would drop it, leaving just n.

Drop Non-Dominant Terms

Just like the constants, when dealing with multiple terms, always focus on the term that grows the fastest as the input increases. For example, in an expression like O(n2 + n + 2n), the n2 term will dominate for large inputs, making the other terms insignificant. Therefore, the overall complexity simplifies to O(n2).

Different Terms for Different Inputs

If an algorithm processes multiple different inputs, you should assign different terms to each one. For instance, if you have two arrays, you might use m for the size of one array and n for the size of the other. This could result in a Big O notation like O(m + n), where both inputs contribute separately to the overall time complexity.

Different Complexities

O(1) Constant Time

No matter the size of the input, the number of steps is constant. Print functions are usually constant. It doesn’t matter if you have 100 inputs; you will always have the same number of operations. Also, it doesn’t matter if it’s 20 or 100 steps; you default it to O(1).

int one = 1        

O(n) aka Linear Rate

As your input increases, the number of operations increases. This means if you have 1 input, it takes one operation; if you have 100, it will increase to 100. So n = size of inputs. Loops are linear time. If you have two loops in a function (not nested) with the same input, the Big O notation will be O(n + n) = O(2n). When you remove the constant value, it defaults to O(n).

   public void PrintAllNames(string[] names) 
    {
        foreach (var name in names)
        {
            Console.WriteLine(name); 
        }
    }        

O(n2) Quadratic Time

This typically occurs with nested loops. The Big O will be O(n*n) = O(n2), which is the same as O(n*m) when considering two different inputs.

public void PrintAllPairs(int[] numbers)
    {
        for (int i = 0; i < numbers.Length; i++)
        {
            for (int j = 0; j < numbers.Length; j++)
            {
                Console.WriteLine($"Pair: {numbers[i]}, {numbers[j]}"); //
            }
        }
    }        

O(n!) Factorial Time

This complexity is best avoided. Algorithms with this time complexity can become impractical very fast as the input size increases.

Understanding time complexity is crucial for assessing algorithm efficiency. Analyzing worst-case scenarios helps make informed algorithm choices for specific problems.