DSA · Foundations

Big-O in Simple English

Big-O describes how an algorithm's work or memory grows as the input grows. Ignore constants and smaller terms; focus on the growth pattern.

Simple summary: Big-O compares how algorithms scale. Count repeated work, keep the fastest-growing term, and report both time and extra space. Example: One loop over 1,000 items is O(n); two nested loops over 1,000 items is about 1,000,000 checks — O(n²).

1. What Big-O means

If the input size is n, how quickly does the amount of work grow? Compare n = 1,000 with n = 1,000,000.

Example: Print every element once → work grows linearly with n → O(n).

2. Common complexities (fastest → slowest)

Big-O	Name	Simple example
O(1)	Constant	Array index access, hash get
O(log n)	Logarithmic	Binary search
O(n)	Linear	One full pass through an array
O(n log n)	Linearithmic	Efficient sorting, such as merge sort
O(n²)	Quadratic	Two nested loops over an array

Rule of thumb: In interviews, aim for O(n) or O(n log n) unless the problem forces worse.

3. Time vs space

Time means how the number of operations grows. Space means how much extra memory grows, excluding the input itself.

Find duplicate in array of n numbers: Sort then scan: Time O(n log n), Space O(1) if in-place Hash set: Time O(n), Space O(n) Trade: pay memory to save time.

4. How to count loops (quick rules)

One loop over n → O(n)
Two nested loops over n → O(n²)
Loop that halves n each time → O(log n)
Outer n, inner log n (e.g. binary search per element) → O(n log n)

5. Worked example — search in sorted array

Linear scan: check every element → O(n).

Binary search: cut search space in half each step → O(log n).

For n = 1,000,000, a linear scan may need about one million checks, while binary search needs about 20. Binary search requires sorted data.

6. One more worked example — keep the largest term

for item in nums: # n operations print(item) for i in 0..n-1: # n × n operations for j in 0..n-1: compare(i, j)

The total is O(n + n²). As n grows, n² dominates, so we report O(n²).

Walkthrough (n = 100): First loop runs 100 times. Second loop runs 100 × 100 = 10,000 times. Total ≈ 10,100 — dominated by 10,000 → O(n²).

7. What to say in interviews

"Brute force is O(n²) time, O(1) space."
"With a hash map I trade O(n) space for O(n) time."
"Dominant term is the nested loop, so O(n²)."

Quick revision

O(1) — index, hash lookup.
O(log n) — binary search.
O(n) — one pass, hash map single loop.
O(n log n) — efficient sort.
O(n²) — nested loops — usually needs optimization.
Always mention both time and space when you optimize.