Big O Notation: The Developer's Practical Guide

Big O Notation: The Developer's Practical Guide

Big O describes how an algorithm's time or space requirements grow as input size grows. In interviews, you're expected to state complexity for every solution you write.

The common complexities

Big O	Name	Example	1M input
O(1)	Constant	Hash map lookup	~1ns
O(log n)	Logarithmic	Binary search	~20 ops
O(n)	Linear	Array scan	~1M ops
O(n log n)	Linearithmic	Merge sort	~20M ops
O(n²)	Quadratic	Bubble sort	~1T ops
O(2ⁿ)	Exponential	Recursive Fibonacci	never

How to analyse code

Rule 1: Drop constants

// O(2n) → O(n)
for (int x : arr) { process(x); }  // n
for (int x : arr) { log(x); }       // n

Rule 2: Drop non-dominant terms

// O(n² + n) → O(n²)
for (int i : arr)              // n
  for (int j : arr) { ... }    // n²

Rule 3: Different inputs = different variables

// O(a + b), NOT O(n)
void foo(int[] a, int[] b) {
    for (int x : a) { ... }  // a
    for (int x : b) { ... }  // b
}

Rule 4: Recursion = check the recurrence

Fibonacci naive: each call branches into two → O(2ⁿ) Fibonacci memoized: each value computed once → O(n)

Space complexity

Space complexity measures additional memory used, not the input itself.

• Iterative array algorithm with a hash map: O(n) space
• Recursive DFS on a tree of height h: O(h) stack space
• In-place sorting: O(1) space

Interview tip

State complexity proactively: "This is O(n log n) time and O(1) space." Then the interviewer knows you know — they don't have to ask.