Big O notation is the reason every post in the Tekraze DSA series ends with a line like “Time O(n), Space O(n)”. If that line ever felt like magic, this helper post is for you. Keep it open in a tab while you solve the daily problems, and come back whenever a complexity looks confusing.
No heavy maths here. Just plain words, small code in Java, Python and Rust, and a few habits that make Big O notation feel obvious.
Also Read: DSA Series Day 1: Two Sum in Java, Python and Rust
What does Big O notation actually mean?
Big O notation tells you how the work grows when the input grows. It does not measure seconds. It answers one question: if I double the input, what happens to the work?
If the work stays the same, that is O(1). If it doubles, that is O(n). If it becomes four times bigger, that is O(n²). Your laptop speed, your language and tiny details don’t matter here. Only the shape of the growth does.
How fast do the common Big O notation classes grow?
This chart says more than a page of theory. Look how quickly O(2ⁿ) and O(n²) shoot up while O(log n) barely moves.
| Complexity | Name | Everyday example | Code example |
|---|---|---|---|
| O(1) | Constant | Opening a book at a bookmark | Array index, hash map lookup |
| O(log n) | Logarithmic | Finding a word in a dictionary by halving | Binary search |
| O(n) | Linear | Reading every page once | Single loop, linear search |
| O(n log n) | Linearithmic | Sorting a deck by splitting and merging | Merge sort, heap sort |
| O(n²) | Quadratic | Everyone in a room shaking hands with everyone | Nested loops over the same array |
| O(2ⁿ) | Exponential | Trying every on/off combo of n switches | Naive recursive Fibonacci, subsets |
| O(n!) | Factorial | Trying every seating order at a dinner table | All permutations, brute force TSP |
A quick feel for sizes: with n = 1,000,000, an O(n log n) solution does about 20 million steps and finishes instantly. An O(n²) solution does a trillion and will time out on any judge.
How do you calculate Big O notation step by step?
You only need six rules. Apply them in order and most problems become easy.
Rule 1: Why does Big O notation drop constants?
A loop that does 3 things per element is O(3n), which we write as O(n). Big O notation ignores constants because they don’t change the shape of growth. Two separate passes over the array are still O(n).
Rule 2: Why does Big O notation drop smaller terms?
O(n² + n + 100) becomes O(n²). When n is huge, the biggest term eats everything else.
Rule 3: When do loops add and when do they multiply in Big O notation?
Loops one after another add. Loops inside each other multiply. Different inputs keep different letters. Looping over array a then array b is O(a + b), and nesting them is O(a × b), not O(n²).
python
for x in a: # O(a)
...
for y in b: # O(b) -> total O(a + b)
...
for x in a:
for y in b: # O(a * b)
...
Rule 4: Why does halving give log n in Big O notation?
If each step cuts the problem in half, you can only halve n about log₂ n times before reaching 1. A million items need only around 20 steps. That is binary search, and any loop like i = i * 2 or n = n / 2.
Rule 5: How do you handle recursion with Big O notation?
Draw a recursion tree. Count how many calls happen and how much work each call does. Total time is roughly calls multiplied by work per call.
Naive Fibonacci makes two calls each time, so the tree doubles at every level and gives O(2ⁿ). Merge sort has log n levels and does O(n) work per level, which gives O(n log n).
Rule 6: What is amortized complexity in Big O notation?
Some operations are usually cheap and occasionally expensive. A dynamic array like Java’s ArrayList, Python’s list or Rust‘s Vec doubles its capacity when full, which costs O(n) once in a while. Spread over all pushes, the average is still O(1). That average over a sequence is called amortized O(1). Hash maps work the same way when they resize.
What does Big O notation look like in real code?
Here are small snippets I ran on my machine before adding them here. Each snippet states its Big O notation in a comment.
Java example with binary search and a HashSet
java
import java.util.*;
public class Complexity {
// O(log n) time, O(1) space
static int binarySearch(int[] a, int t) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == t) return mid;
if (a[mid] < t) lo = mid + 1; else hi = mid - 1;
}
return -1;
}
// O(n) time, O(n) space
static boolean hasDuplicate(int[] a) {
Set<Integer> seen = new HashSet<>();
for (int x : a) if (!seen.add(x)) return true;
return false;
}
public static void main(String[] args) {
int[] a = {1, 3, 5, 7, 9, 11};
System.out.println(binarySearch(a, 7) + " " + hasDuplicate(new int[]{1, 2, 2}));
}
}
Python example with slow and memoized Fibonacci
python
# O(2^n) time, O(n) stack space
def fib_slow(n):
if n < 2:
return n
return fib_slow(n - 1) + fib_slow(n - 2)
# O(n) time, O(n) space thanks to memo
def fib_memo(n, memo=None):
memo = {} if memo is None else memo
if n < 2:
return n
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print(fib_slow(20), fib_memo(80))
Same problem, two complexities. Memoization turns the exponential tree into a straight line because every value is computed only once.
Rust example with nested loops and Vec push
rust
// O(n^2) time, O(1) space
fn count_pairs(nums: &[i32], target: i32) -> usize {
let mut count = 0;
for i in 0..nums.len() {
for j in (i + 1)..nums.len() {
if nums[i] + nums[j] == target { count += 1; }
}
}
count
}
// Amortized O(1) push, O(n) total for n pushes
fn build(n: usize) -> Vec<usize> {
let mut v = Vec::new();
for i in 0..n { v.push(i); }
v
}
fn main() {
println!("{} {}", count_pairs(&[1, 2, 3, 4, 5], 6), build(1000).len());
}
What is space complexity in Big O notation?
Big O notation covers memory as well as time. Space complexity is how much extra memory your solution needs as the input grows. Most interviewers mean auxiliary space, which is the memory you create on top of the input. Sorting in place uses O(1) extra space, while copying the array uses O(n).
Three things count toward it:
- New data structures. A hash map holding n items is O(n).
- The recursion stack. Every call that hasn’t returned yet sits in memory. Recursion n levels deep costs O(n) space even if you allocate nothing. Balanced tree recursion costs O(log n).
- Output. Usually not counted, but say so out loud if you exclude it.
This is why naive recursive Fibonacci is O(2ⁿ) time but only O(n) space. The tree is huge, but only one path from root to leaf lives on the stack at a time.
What is the difference between best, average and worst case?
Linear search finds the target at index 0 in the best case, O(1), and at the end or not at all in the worst case, O(n). Quick sort is O(n log n) on average but O(n²) when pivots are chosen badly. Hash map lookups are O(1) on average and O(n) in the rare worst case when everything collides.
When someone says just “Big O notation”, they usually mean the worst case. The exception is a structure famous for its average case, like a hash map.
How do we calculate Two Sum with Big O notation?
Let’s apply the rules to the problem from DSA Series Day 1, brute force versus hash map.
python
# Brute force
for i in range(n): # runs n times
for j in range(i + 1, n): # runs n-1, n-2, ... 1 times
if nums[i] + nums[j] == target:
return [i, j]
The inner loop runs (n−1) + (n−2) + … + 1 times, which is n(n−1)/2. Expand it to n²/2 − n/2. Drop the constant ½ and the smaller term n, and you get O(n²) time. We only use a few variables, so it is O(1) space.
python
# Hash map
seen = {}
for i, num in enumerate(nums): # runs n times
need = target - num # O(1)
if need in seen: # O(1) average
return [seen[need], i]
seen[num] = i # O(1) amortized
One loop of n steps, each doing O(1) work, gives O(n) time. The map can hold up to n entries, so O(n) space. We traded memory for speed, and that trade shows up in most problems in this series.
What is the quick Big O notation cheat sheet?
Bookmark these two tables for quick Big O notation lookups. They cover most of what interviews ask.
Data structure operations
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Dynamic array (append) | O(1) | O(n) | O(1) amortized | O(n) |
| Linked list | O(n) | O(n) | O(1) at head | O(1) at head |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) |
| Hash map / set | n/a | O(1) avg | O(1) avg | O(1) avg |
| Balanced BST (TreeMap, BTreeMap) | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary heap | O(1) peek | O(n) | O(log n) | O(log n) pop |
Sorting algorithms
| Algorithm | Best | Average | Worst | Extra space |
|---|---|---|---|---|
| Bubble / Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) |
| Built-in sort (Timsort, pdqsort) | O(n) | O(n log n) | O(n log n) | O(n) or O(log n) |
What are the best tips for spotting Big O notation in interviews?
These habits make Big O notation quick to read under pressure.
- Count the loops first. One loop over the input is usually O(n). Two nested ones are O(n²).
- Look for halving. Sorted input, binary search or a
midin the code means log n is hiding there. - Remember the sorting floor. Any comparison sort costs O(n log n), so sorting first means you can’t beat that.
- Hidden loops count.
list.contains,x in list, substring, string concatenation in a loop and slicing all cost O(n). - Use constraints as a hint. n up to 10⁵ or 10⁶ wants O(n) or O(n log n). n around 20 allows O(2ⁿ). n around 10 allows O(n!).
- Watch for double recursion. Two calls and no memo screams exponential. Memoization often brings it down to O(n) or O(n²).
- Say both. Always give time and space together, and mention the trade you made.
What common mistakes break Big O notation answers?
Even experienced coders slip on Big O notation in a few predictable ways.
- Calling two different inputs n and writing O(n²) instead of O(a × b).
- Forgetting the recursion stack when stating space.
- Treating hash map lookups as guaranteed O(1) instead of average O(1).
- Thinking two separate loops make O(n²). They make O(n).
- Ignoring the cost of built-in methods like sort, slice or contains.
- Mixing up best case with the general complexity.
How will this helper fit the rest of the series?
Every daily DSA post will link back here whenever we talk about complexity. Read this once, then try to guess the Big O notation of each day’s solution before you scroll down. That small habit builds interview intuition faster than anything else.
Pick one problem you solved recently and work out its time and space now. Then check your answer against the cheat sheet above.
Frequently asked questions
What is Big O notation in simple words?
Big O notation describes how the work or memory of a solution grows as the input size grows. It ignores machine speed and constants and focuses on the shape of growth.
Is O(n log n) better than O(n²)?
Yes. For large inputs O(n log n) grows far slower. With a million items it is about 20 million steps against a trillion.
Does recursion use extra space?
Yes. Every pending call sits on the call stack, so recursion depth d costs O(d) space even if you create no data structures.
Why is hash map lookup O(1)?
A hash function jumps straight to the bucket that holds the key, so the average lookup is constant time. In rare worst cases with many collisions it can degrade to O(n).
How do I find the time complexity of my code quickly?
Count loops and how they nest, look for halving, include the cost of built-in calls, then drop constants and smaller terms.
