DSA · INTERVIEW & OA PREP

Topic 6 of 12

Time & Space Complexity

You will be asked 'what's the complexity?' after nearly every problem. Fluency with Big-O — and with the trade-off between time and space — is a baseline expectation, not an advanced topic.

Key concepts

• Big-O describes growth as input grows; drop constants and lower-order terms.
• Common classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
• Hash maps trade O(n) space for O(1) lookups — name the trade-off.
• Recursion adds O(depth) stack space even when it looks 'in place'.

Questions that get asked

• What's the time complexity of your solution, and can you do better?
• Compare O(n log n) sorting vs O(n) hashing for a dedup problem.
• Why is binary search O(log n)?
• What's the space complexity of your recursion?