Every coding question has many possible solutions; the test — and the interviewer — rewards the one that scales. Big-O notation is the language for describing how an algorithm's running time and memory grow as the input grows.
What Big-O measures
Big-O describes the growth rate of an algorithm in the worst case as the input size n becomes large. We keep only the fastest-growing term and drop constants — so 3n + 7 is simply O(n).
The complexity classes you must know
| Notation | Name | Typical source |
|---|---|---|
| O(1) | constant | one direct operation |
| O(log n) | logarithmic | halving each step (binary search) |
| O(n) | linear | one pass over n items |
| O(n log n) | linearithmic | good sorts (merge, heap) |
| O(n^2) | quadratic | nested loop over n |
| O(2^n) | exponential | raw recursion over subsets |
| O(n!) | factorial | all permutations |
Nested loops multiply
for i = 0 to n-1:
for j = 0 to n-1:
print(i, j)
// runs n x n times -> O(n^2)⚡ The edge
- Count the loops, drop the constants. A single pass is O(n); a loop nested inside another over the same n is O(n^2); halving the problem each step is O(log n).
- Constants and lower-order terms disappear: O(2n + 5) is just O(n), and O(n^2 + n) is just O(n^2).
Worked example
What is the time complexity of this code?
sum = 0
for i = 1 to n:
for j = 1 to n:
sum = sum + 1- The outer loop runs n times, and for each outer pass the inner loop runs n times.
- Total operations = n x n = n^2.
- Dropping constants, the complexity is O(n^2).
Answer: O(n^2)
Worked example
What is the time complexity?
i = n
while i > 1:
i = i / 2 // integer division- Each step halves i: n, n/2, n/4, ... down to 1.
- The number of times you can halve n before reaching 1 is about log₂(n).
- So the loop runs about log n times -> O(log n).
Answer: O(log n)
⚠ Watch out
- Big-O is the worst case unless stated; average and best cases can differ.
- Drop constants and lower terms: O(500) is O(1), O(n/2) is O(n).
- Don't forget space complexity — recursion uses stack memory of O(depth).