Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is used to classify algorithms according to how their running time or space requirements grow as the input size grows. Understanding Big O is crucial for technical interviews as it shows you can think about the efficiency of your code.

Why is Big O Important?

Imagine two algorithms that do the same thing. How do you know which one is better? Big O provides a standardized way to compare them. It's not about measuring the exact time an algorithm takes, which can vary based on the computer's hardware, but about understanding how the performance changes with the input size.

• O(1) - Constant Time: The algorithm takes the same amount of time, regardless of the input size.

  • Example: Accessing an element in an array by its index. array[5] takes the same time whether the array has 10 elements or 10 million.

• O(log n) - Logarithmic Time: The time it takes grows logarithmically with the input size. This is incredibly efficient for large datasets because the time taken increases very slowly.

  • Example: Binary search in a sorted array. With each step, you cut the search space in half.

• O(n) - Linear Time: The runtime is directly proportional to the size of the input. If the input size doubles, the runtime roughly doubles.

  • Example: Searching for an element in an unsorted array by checking each element one by one.

• O(n log n) - Log-Linear Time: A very common complexity for efficient sorting algorithms.

  • Example: Merge Sort and Quick Sort.

• O(n²) - Quadratic Time: The runtime is proportional to the square of the input size. This becomes slow very quickly.

  • Example: A nested loop where you compare every element of a list to every other element, like in a simple bubble sort.

• O(2^n) - Exponential Time: The runtime doubles with each addition to the input dataset. These algorithms are extremely slow and are generally not scalable.

  • Example: A recursive calculation of Fibonacci numbers without memoization.

How to Calculate Big O

When analyzing an algorithm, you should focus on the "worst-case scenario" and drop constants and less significant terms.

def find_sum_and_product(numbers):
  sum = 0
  for num in numbers:
    sum += num  # This part is O(n)

  product = 1
  for num in numbers:
    product *= num # This part is also O(n)

  return sum, product

In the example above, you have two separate loops. The first loop is O(n) and the second is also O(n). The total complexity is O(n + n) = O(2n). However, in Big O, we drop the constant, so the final complexity is just O(n).

Now, consider a nested loop:

def print_pairs(numbers):
  for num1 in numbers:      # Outer loop runs n times
    for num2 in numbers:  # Inner loop runs n times for each outer loop iteration
      print(num1, num2)

Here, the inner loop runs n times for each iteration of the outer loop. This results in n * n operations, so the complexity is O(n²).

Conclusion

In a coding interview, when you present a solution, you will almost always be asked, "What is the time and space complexity of your algorithm?" Being able to confidently analyze your code and explain your reasoning in terms of Big O notation is a sign of a strong engineering candidate. Use our Tutor tool to get a deeper dive into analyzing more complex algorithms.