Big O Notation Explained with Real Interview Code

Big O notation explained with time complexity examples in Python: how to derive complexity, read constraints, and avoid hidden costs in interviews.

By InternHack Team · 2026-09-29 · 9 min read · DSA

This guide is for students who have seen Big O in a lecture but still hesitate when an interviewer asks "what is the complexity of this?". You will learn the common classes with code, a repeatable way to derive complexity from loops and recursion, and how to use problem constraints to choose an algorithm before you write a line.

What Big O actually measures

Big O describes how the running time or memory of an algorithm grows as the input size n grows. It ignores constants and lower-order terms, so 3n + 20 is O(n) and n² + n is O(n²). It gives an upper bound on growth, and in interviews people almost always mean the worst case unless they say otherwise.

Two things to keep straight. Big O is not the same as real speed: an O(n) algorithm with a huge constant can lose to an O(n log n) one on small inputs. And n must be defined. For a graph, complexity is usually written in V and E. For two arrays, it may be O(n + m). Always say what n stands for.

The common classes, with code

O(1): constant

def first_or_none(arr):
    return arr[0] if arr else None

Array indexing, dictionary lookup (average), and pushing to a stack are O(1). The time does not depend on input size.

O(log n): halving the problem

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Each iteration halves the search range, so you need about log₂ n steps. For n = 1,000,000 that is around 20 steps.

O(n): one pass

def max_value(arr):
    best = arr[0]
    for x in arr:
        best = max(best, x)
    return best

O(n log n): sort-like work

Sorting with a comparison sort is O(n log n). So is merge sort, and so is "sort first, then scan". Building a heap is O(n), but pushing n items one at a time is O(n log n).

O(n²): nested loops over the same input

def has_duplicate_bruteforce(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

The inner loop runs n-1, n-2, ... 1 times. That sums to about n²/2, which is O(n²). Compare with the version that uses a set:

def has_duplicate(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

This is O(n) time and O(n) space. You traded memory for time, which is the most common improvement in interviews.

O(2ⁿ): branching recursion

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

Every call makes two more calls, so the number of calls roughly doubles with each level of depth. This naive Fibonacci is exponential. Add memoization and it becomes O(n), because each value is computed once:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

Subset generation is also O(2ⁿ), since a set of n elements has 2ⁿ subsets.

O(n!): permutations

Generating all orderings of n items produces n! results. It shows up in brute-force travelling salesman and in "generate all permutations" problems. It is only workable for n up to about 10 to 11.

How to derive complexity from code

Use this checklist rather than guessing.

1. Sequential blocks add. Two loops one after another, each O(n), give O(n) after dropping constants. A loop of O(n) followed by a sort of O(n log n) gives O(n log n), because the larger term wins.
2. Nested blocks multiply. A loop of n iterations containing a loop of m iterations is O(n · m). Check whether the inner bound depends on the outer variable, as in the triangular loop above.
3. Halving or doubling gives log. If the loop variable is multiplied or divided by a constant each step (i *= 2), the loop runs O(log n) times.
4. Function calls cost what the function costs. A call to sorted() inside a loop is O(n log n) per iteration.
5. Recursion: count calls times work per call. Draw the recursion tree. Depth times branching factor tells you the number of calls.

A quick example of rule 3 combined with rule 2:

def pairs_with_doubling(n):
    count = 0
    for i in range(n):        # n iterations
        j = 1
        while j < n:          # log n iterations
            count += 1
            j *= 2
    return count

This is O(n log n).

Recurrences and the master theorem (lightly)

Divide and conquer algorithms give recurrences of the form T(n) = a·T(n/b) + f(n), where a is the number of subproblems, b is how much the input shrinks, and f(n) is the work to split and combine.

Compare f(n) with n^(log_b a):

• If the recursive part dominates, T(n) = O(n^(log_b a)). Example: T(n) = 8T(n/2) + n² gives O(n³).
• If both are equal in growth, you get an extra log factor. Merge sort: T(n) = 2T(n/2) + n gives O(n log n).
• If the combine work dominates, T(n) = O(f(n)). Example: T(n) = T(n/2) + n gives O(n).

Binary search is T(n) = T(n/2) + 1, which gives O(log n). You do not need to memorise the formal cases for most interviews. Being able to say "two halves, linear merge, so n log n" is enough.

Amortized analysis: the dynamic array

Appending to a Python list, a Java ArrayList or a C++ vector is described as O(1), but sometimes the underlying array is full and must be copied into a larger one, which costs O(n).

Suppose the array doubles each time it fills. Copies happen at sizes 1, 2, 4, 8, ... up to n. The total copying work across n appends is about 1 + 2 + 4 + ... + n, which is less than 2n. Spread over n appends, that averages to O(1) per append. This is amortized O(1): a single operation may be expensive, but the average over a sequence is constant.

Note this is different from average-case analysis. Amortized bounds hold for any sequence of operations, with no probability involved.

Space complexity

Space complexity counts the extra memory your algorithm uses, not the input itself. Things to count:

• New arrays, sets and dictionaries you create
• The recursion stack: a recursive DFS on a path-like tree uses O(n) stack space; binary search written recursively uses O(log n)
• Slices that copy data (Python arr[1:] creates a new list)

def sum_recursive(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)   # O(n) stack

The iterative loop version uses O(1) extra space. Interviewers often ask "can you do it in O(1) space?", which usually means replacing recursion with iteration or reusing the input array.

Reading constraints: the 10^8 rule of thumb

A common rule of thumb is that a typical judge or interview machine handles about 10^8 simple operations per second in a compiled language, and noticeably fewer in Python. Treat it as an estimate. Use it to reject algorithms that clearly cannot work.

If the statement says n ≤ 10^5 and your idea is a double loop, that is 10^10 operations. You need something better before coding. The table is a starting guide, and constants matter. A heavy O(n log n) in Python with n = 10^6 may still be slow.

This is the habit interviewers like: read the constraints first, name the target complexity aloud, and only then pick the approach. For practice on choosing techniques, see the DSA problems, and start with DSA foundations if arrays and hashing still feel new.

Common traps and hidden costs

Most wrong complexity claims come from operations that look cheap but are not.

String concatenation in a loop. In Python, s += ch can create a new string each time, so building a string of length n in a loop may cost O(n²) in the worst case (CPython sometimes optimises this, but you cannot rely on it). The safe pattern:

parts = []
for ch in data:
    parts.append(ch)
result = "".join(parts)   # O(n)

In Java, use StringBuilder instead of += on String, since strings are immutable. In C++, std::string append is amortized O(1), so the trap is milder there.

The in operator on a list. x in my_list scans the list, so it is O(n). Inside a loop over n items, that becomes O(n²). Convert the list to a set first and membership becomes O(1) on average:

allowed = set(items)          # O(n) once
count = sum(1 for x in queries if x in allowed)

List operations that shift elements. list.insert(0, x) and list.pop(0) are O(n) because everything shifts. For a queue use collections.deque, where both ends are O(1).

Slicing and copying. arr[1:] copies n-1 elements. A recursive function that slices its input on every call turns an O(n) idea into O(n²).

Nested library calls. sorted() inside a loop, max(arr) inside a loop, sum(arr[:i]) inside a loop: each is a hidden inner loop. Prefix sums or a running maximum fix most of these.

Hash collisions and worst cases. Hash map operations are O(1) on average and O(n) in a degenerate worst case. In interviews, quote average O(1) but be ready to say why.

A Java and C++ contrast on the same idea, checking a value in a collection:

List<Integer> list = new ArrayList<>();
list.contains(5);   // O(n)

Set<Integer> set = new HashSet<>();
set.contains(5);    // O(1) average

std::vector<int> v;
std::find(v.begin(), v.end(), 5);   // O(n)

std::unordered_set<int> s;
s.count(5);                         // O(1) average
std::set<int> t;
t.count(5);                         // O(log n), balanced tree

The last line is a common trap in C++: std::set and std::map are ordered trees with O(log n) operations, while unordered_set and unordered_map are hash-based.

How to state complexity in an interview

A short, complete answer sounds like this: "Time is O(n log n) because of the sort, then a single pass. Space is O(n) for the hash map. If the input were already sorted, I could use two pointers and drop the extra space to O(1)."

Notice the pattern: give time, give space, name the dominant step, and mention one improvement or trade-off. Practise saying it aloud after every problem you solve. If you are following a study schedule, our 90-day internship interview plan puts complexity practice in week 1. For core CS follow-ups on sorting and data structures, browse the interview prep hub and the roadmaps.

FAQ

What is Big O notation in simple terms?

Big O describes how the running time or memory of an algorithm grows as the input size grows. It drops constants and smaller terms, so it focuses on the shape of growth, such as linear, quadratic or logarithmic. It is usually quoted for the worst case.

How do I find the time complexity of a program?

Count how many times the dominant statements run as a function of n. Add sequential blocks, multiply nested loops, treat halving loops as log n, and for recursion draw the call tree or write a recurrence. Then keep only the largest term.

What is the difference between O(n) and O(log n)?

O(n) grows in direct proportion to input size, so doubling the input doubles the work. O(log n) grows very slowly: doubling the input adds only one extra step. Binary search on a sorted array is the standard O(log n) example.

Why is appending to a list O(1) if resizing costs O(n)?

Resizing happens rarely, because the array capacity grows geometrically. Spread across many appends, the total copying cost averages out to a constant per append. This is called amortized O(1).

How many operations can I do per second in an interview problem?

A common estimate is about 10^8 simple operations per second in compiled languages, and fewer in Python. Use it to check if an approach fits the constraints, for example that n up to 10^5 needs roughly O(n log n) or better.