10 Big O Interview Questions Every Developer Must Answer

Big-O notation (also called "asymptotic growth" notation) is a relative representation of the complexity of an algorithm. It shows how an algorithm scales based on input size. We use it to talk about how thing scale. Big O complexity can be visualized with this graph:

O(n2) means for every element, you're doing something with every other element, such as comparing them. Bubble sort is an example of this.

O(log n) means for every element, you're doing something that only needs to look at log N of the elements. This is usually because you know something about the elements that let you make an efficient choice (for example to reduce a search space). The most common attributes of logarithmic running-time function are that:

• the choice of the next element on which to perform some action is one of several possibilities, and
• only one will need to be chosen

or

• the elements on which the action is performed are digits of n

Most efficient sorts are an example of this, such as merge sort. ​It is O(log n) when we do divide and conquer type of algorithms e.g binary search. Another example is quick sort where each time we divide the array into two parts and each time it takes O(N) time to find a pivot element. Hence it N O(log N)

Plotting log(n) on a plain piece of paper, will result in a graph where the rise of the curve decelerates as n increases:

The fact is it's difficult to determine the exact runtime of an algorithm. It depends on the speed of the computer processor. So instead of talking about the runtime directly, we use Big O Notation to talk about how quickly the runtime grows depending on input size.

With Big O Notation, we use the size of the input, which we call n. So we can say things like the runtime grows “on the order of the size of the input” (O(n)) or “on the order of the square of the size of the input” (O(n2)). Our algorithm may have steps that seem expensive when n is small but are eclipsed eventually by other steps as n gets larger. For Big O Notation analysis, we care more about the stuff that grows fastest as the input grows, because everything else is quickly eclipsed as n gets very large.

Space complexity means the amount of space the algorithm needs to run.

Example 1: Sorting-Algorithms
All sorting algorithms need at least O(n) space to save the list (of length n) they have to sort

1. Bubblesort (and most other sorting algorithms too) can work in-place, this means that it needs no more space as it needs to save the list. (just searching two elements in the wrong order and swaping them)
2. Stupid-Sort lists all permutations of the input list (and saves them) and then searching the sorted one. Since there are n! permutations this algorithm needs O(n * n!) space.

Example 2: Number representation
A number n can be saved in different ways:

1. binary (or any other base ≥2): this needs O(log n) space, due to n = 2log n
2. unary: here you write n as a sum of ones (n = 1 + 1 + 1 + ... + ... + 1) and you have to save every one. So this needs O(n) space, due to n = n ⋅ 1.

This is O(n2) (or Quadratic complexity) since for each pass of the outer loop (O(n)) we have to go through the entire list again so the n's multiply leaving us with n squared.

If you do an operation say a million times, you don't really care about the worst-case or the best-case of that operation - what you care about is how much time is taken in total when you repeat the operation a million times. Essentially amortised time means "average time taken per operation, if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else.

A common example is the dynamic array. If we have already allocated memory for a new entry, adding it will be O(1). If we haven't allocated it we will do so by allocating, say, twice the current amount. This particular insertion will not be O(1), but rather something else.

What is important is that the algorithm guarantees that after a sequence of operations the expensive operations will be amortised and thereby rendering the entire operation O(1).

Because you are usually just interested in the worst case when analyzing the performance. Thus, knowing the upper bound is sufficient. When it runs faster than expected for a given input - that is ok, it's not the critical point. It's mostly negligible information.

Some algorithms don't have a tight bound at all. See quicksort for example which is O(n2) and Omega(n). Moreover, tight bounds are often more difficult to compute.