Big O Notation Explained: Time and Space Complexity

Blog / Big O Notation Explained: Time and Space Complexity

What actually is big O notation? And why do interviewers always ask for it?

Why Not Measure in Seconds

You might be tempted to just time your code in seconds. But timing code depends on the machine, the programming language, and what else is running.This makes it impossible to compare algorithms fairly.This is where Big O notation comes in. Big O describes how the number of steps grows as the input size, n, grows. It provides an upper bound on that growth, written as a mathematical function of n.

O(1): No Loop

O(1) is also known as constant time. Here, the number of steps does not change as n gets larger. A classic example is reading an element from an array by its index.

python

def get_first(arr):
    return arr[0]

No matter how big arr gets, ten items or ten million, this always does one step: it returns the first element. The work never grows, so it is O(1).

O(n): One Loop

O(n) means linear time. This happens when you have one loop over the input. The number of steps grows in a straight line with n.Finding the maximum value in an array is a perfect example.

python

maximum = arr[0]
for num in arr:
    if num > maximum:
        maximum = num

To be sure we have the largest number, we have to look at every item once. Ten items means ten checks, and a million items means a million checks. The work grows exactly as fast as the input, so it is O(n).

O(n²): Nested Loops

Sometimes you need to compare every item against every other item. This introduces nested loops.A loop inside a loop over the same input does n times n steps. We call this O(n²) or quadratic time. Doubling your input size makes the algorithm four times slower.A common example is comparing every pair to find a duplicate.

python

for i in range(n):
    for j in range(n):
        if i != j and arr[i] == arr[j]:
            return True

For each item, the inner loop checks it against every item in the array. Ten items means ten times ten, a hundred checks. A thousand items means a million checks. That is why nested loops are O(n²).

O(log n): Halving

O(log n) is logarithmic time. It describes an algorithm where each step halves what is left to check.A great example is binary search on a sorted array. If you have a million items, finding your target takes only about 20 steps.

python

while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: left = mid + 1
    else: right = mid - 1

Each time round the loop, we check the middle item. If it is not the target, we throw away the half that cannot contain it.

The O(log n) curve and a million items halving down to one in about 20 checks

A million items becomes half a million, then a quarter of a million, and so on, until about 20 checks later only one item is left. That is O(log n).

O(n log n): Halving at Every Level

O(n log n) means doing O(log n) levels of O(n) work. You will see this as the cost of efficient sorts like merge sort.Merge sort keeps splitting the array in half until every piece is a single item. Just like binary search, that takes about log n levels.

Merge sort splitting eight numbers over log n levels, then merging n items at every level

Then it merges the pieces back together in order, and at every level it touches all n items once. So n items, log n times, gives O(n log n).

O(2ⁿ): Every Call Branches in Two

On the extreme end, we have exponential time or O(2ⁿ). This usually happens with a recursive function that calls itself twice per call.The naive Fibonacci algorithm is a famous example. Every time n grows by just one, the amount of work doubles.

python

def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Every call to fibonacci makes two more calls, and each of those makes two more.

The call tree of fibonacci(4): 1 call, then 2, then 4

The calls branch out like a tree that gets roughly twice as wide at every level, so adding one to n roughly doubles the work. That is O(2ⁿ).

Dropping Constants and Lower-Order Terms

When calculating Big O, we only keep the fastest growing term. We also drop all constant multipliers.This is because for very large values of n, the smaller details stop mattering.Take two separate loops, one after the other:

python

for num in arr:
    print(num)
for num in arr:
    print(num * 2)

Each loop goes through all n items, so this is technically 2n steps, written O(2n). But it is still a straight line: double the input and the work still just doubles. We drop the constant two and call it O(n).Now add a single loop after a nested loop:

python

for i in range(n):
    for j in range(n):
        print(i, j)
for i in range(n):
    print(i)

The nested loops do n² steps and the last loop does n more, so n² + n. With a thousand items, that is a million steps plus just a thousand extra, about 0.1 percent.The n² dominates the growth curve, so we drop the smaller n and call it O(n²).

Time vs Space Complexity

So far we have focused on time, but algorithms also consume memory. This brings us to space complexity.The exact same notation describes how extra memory usage grows with n. Building a new array of size n takes O(n) space. Swapping elements in place takes O(1) space.You often trade space for time. Instead of using nested loops to find a duplicate in O(n²) time and O(1) space, you can use a hash set.The hash set finds a duplicate in O(n) time, but it costs O(n) space to store the seen items.

Best, Average and Worst Case

An algorithm might run faster or slower depending on the exact input.If you do a linear search, you might find your item on the very first try. This is the best case. Or the item might be at the very end, which is the worst case.In interviews, Big O usually refers to the worst case scenario. However, there are exceptions where the average case matters more.For example, quicksort runs in O(n log n) time on average, but drops to O(n²) time in the worst case.

Recap

Here are the main growth curves from fastest to slowest.

Complexity	How to spot it in code	Example
O(1)	No loop	Reading an array element
O(log n)	Halving the input	Binary search
O(n)	One loop	Finding the maximum
O(n log n)	O(log n) levels of O(n) work	Merge sort
O(n²)	Nested loops	Comparing every pair
O(2ⁿ)	Two recursive calls per step	Naive Fibonacci

You should now be able to look at a short piece of code in an interview and state its time and space complexity. Practice analyzing small functions on the DSA question collection to get completely comfortable with these concepts.

About TechPrep

Never walk into a technical interview unprepared again. TechPrep empowers software engineers to stop guessing and start getting offers. We provide the exact questions asked by tech companies across Data Structures & Algorithms, System Design, Low-Level Design & AI coding rounds. Don't leave your career up to chance. Join thousands of engineers who have successfully navigated the tech hiring maze and landed roles at top tech companies.