What is Big O Notation?
Learn Big O notation with simple examples — O(1), O(log n), O(n), O(n²) — how to derive complexity, common mistakes and DSA interview questions with answers.
Expected Interview Answer
Big O notation describes how an algorithm’s running time or memory usage grows as the input size grows, focusing on the dominant term and ignoring constant factors.
It gives an upper bound on growth rate so algorithms can be compared independently of hardware. Common classes, from fastest-growing suitability to slowest, are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n²) quadratic, and O(2ⁿ) exponential. Interviewers use it to check you can reason about scalability, not just correctness.
- Compares algorithms independent of hardware
- Predicts behavior at scale
- Guides data-structure choice
AI Mentor Explanation
Finding a player’s score in an unsorted scorebook means scanning page by page — double the matches, double the search time. That is O(n). But if the book is indexed alphabetically, you jump straight to the right page no matter how thick the book gets — closer to O(log n). Big O captures exactly this: not how many seconds the lookup takes, but how the effort grows as the season gets longer.
Step-by-Step Explanation
Step 1
Count dominant operations
Identify the operation that runs most as input size n grows.
Step 2
Drop constants
3n + 10 and n both grow linearly — both are O(n).
Step 3
Keep the largest term
n² + n log n + n is O(n²); the fastest-growing term dominates.
Step 4
State best/average/worst
Quicksort is O(n log n) average but O(n²) worst case — say which you mean.
What Interviewer Expects
- Definition in terms of growth rate, not raw speed
- Ranking of common complexity classes
- Complexity of everyday operations (hash lookup, binary search, sorting)
- Awareness of space complexity, not just time
Common Mistakes
- Saying Big O measures exact running time in seconds
- Forgetting to drop constants and lower-order terms
- Quoting only worst case when average case is asked
- Ignoring space complexity entirely
Best Answer (HR Friendly)
“Big O notation is a way to describe how an algorithm scales — how much slower it gets as the data grows. It lets engineers compare approaches and choose ones that stay fast as systems and datasets grow.”
Code Example
def linear_search(items, target): # O(n)
for i, item in enumerate(items):
if item == target:
return i
return -1
def binary_search(sorted_items, target): # O(log n)
lo, hi = 0, len(sorted_items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sorted_items[mid] == target:
return mid
if sorted_items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Follow-up Questions
- What is the time complexity of common sorting algorithms?
- What is the difference between Big O, Big Theta and Big Omega?
- What is amortized time complexity?
- Why is hash table lookup considered O(1)?
MCQ Practice
1. What is the time complexity of binary search on a sorted array?
Binary search halves the search space on each step, giving logarithmic time.
2. Which grows fastest as n increases?
Exponential O(2ⁿ) outgrows every polynomial class as n increases.
3. What is O(3n + 5) simplified?
Big O drops constant factors and lower-order terms, leaving O(n).
Flash Cards
O(1)? — Constant time — cost does not grow with input size (e.g. hash lookup).
O(log n)? — Logarithmic — halving the problem each step (e.g. binary search).
O(n log n)? — The best comparison-based sorting can do (merge sort, heapsort).
O(n²)? — Quadratic — all-pairs work (e.g. bubble sort, nested loops).