Core Concept Mastery • DSA Module
A quick-reference guide covering everything from this module: Time Complexity, Space Complexity, and Best/Average/Worst Case analysis.
Time = count steps. Space = count extra memory. Big-O = worst case guarantee.
Time Complexity
Count operations. Loops = O(n). Nested loops = O(n²). No loops = O(1).
Drop constants: 5n → O(n). Keep biggest term: n² + n → O(n²).
Space Complexity
Count extra memory. Few variables = O(1). New array of size n = O(n).
Recursion uses stack space: n calls deep = O(n) space.
Best / Average / Worst
Ω (Omega) = Best Case. Θ (Theta) = Average. O (Big-O) = Worst Case.
Always plan for worst case. Big-O is the default.
O(1) — Constant — Instant, no matter the input size
O(log n) — Logarithmic — Cuts problem in half each step
O(n) — Linear — Visits every item once
O(n log n) — Linearithmic — Efficient sorting
O(n²) — Quadratic — Nested loops, avoid for big data
O(2^n) — Exponential — Only for tiny inputs, extremely slow
Time Complexity — The Key Ideas:
Space Complexity — The Key Ideas:
Best, Average, Worst Case — The Key Ideas:
Interview Tip:
Always state the Time AND Space complexity of your solution. Show you think about both dimensions.
Use this as a revision sheet before interviews or exams. All the key ideas in one place.
"What is the one thing to always remember about complexity?"
Big-O measures SCALABILITY (growth), not speed. It tells you how performance changes as input grows.