📈 Time and Space Complexity — Big O Notation for Beginners
Understand Big O notation, time complexity and space complexity. Learn O(1), O(log n), O(n), O(n log n), O(n²) with C++ examples — your foundation for DSA interviews.
Big O notation describes how an algorithm's running time (or memory usage) grows as the input size grows. It's the language of algorithm analysis — and the language of technical interviews.
📊 The common classes
O(1)— constant. Array access, hash map lookup.O(log n)— logarithmic. Binary search.O(n)— linear. Single loop over n items.O(n log n)— linearithmic. Efficient sorts.O(n²)— quadratic. Nested loops over n.O(2ⁿ)— exponential. Naive recursion (Fibonacci).O(n!)— factorial. Brute-force permutations.
📦 Space complexity
Same idea but for memory. Storing all n items in a vector = O(n).
💡 Drop constants and lower terms
3n + 5 → O(n). n² + n → O(n²).
💻 Code Examples
O(1) — array index
int first = arr[0];Output:
Constant time.
O(n) — finding the maximum
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}Output:
One pass over n items.
O(n²) — bubble sort
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j+1]) std::swap(arr[j], arr[j+1]);
}
}Output:
Nested loops over n.
⚠️ Common Mistakes
- Counting EVERY operation literally — Big O is asymptotic, drop constants and lower terms.
- Saying 'this is O(n)' for a nested loop — that's O(n²).
- Confusing time with space.
- Ignoring average vs worst case — quicksort is O(n log n) average but O(n²) worst case.
- Stopping at correctness — interview answers ALWAYS need a complexity claim.
🎯 Interview Questions
Real questions asked at top product and service-based companies.
Q1.What is Big O notation?Beginner
A way to describe how the running time (or memory usage) of an algorithm grows as the input size n grows. It captures the upper bound of the dominant term.
Q2.What's the complexity of binary search?Beginner
O(log n). Each step halves the search space. Requires sorted input.
Q3.What's the difference between best, average, and worst case?Intermediate
Best: minimum operations. Average: expected on typical input. Worst: maximum on adversarial input. Big O usually refers to worst case.
Q4.Why is O(n log n) considered efficient for sorting?Intermediate
Comparison-based sorting has a proven lower bound of Ω(n log n). Algorithms like mergesort hit this bound.
Q5.What's the difference between O(n) space and in-place?Advanced
O(n) space algorithms allocate memory proportional to input size. In-place algorithms use O(1) extra space.
🧠 Quick Summary
- Big O = how run-time/memory scale with input size n.
- Common: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
- Drop constants and lower-order terms.
- Time and space complexities are separate.
- Always state complexity in interviews.