Big O notation

Overview

Big O tells you how the runtime or memory grows as input size increases.

Important ones

• O(1): constant
• O(log n): binary search, balanced BST operations
• O(n): linear scan
• O(n log n): merge sort, heap sort, efficient sorting
• O(n^2): nested loops
• O(2^n): recursion with repeated subproblems
• O(n!): very expensive, usually not expected in interviews

Interview guidance

Usually, the best answer is the one with the lowest practical complexity under constraints.

Problems to practice

• What is the time complexity of nested loops?
• Why is hash map lookup O(1) average time?
• Why is DFS O(V + E) for adjacency list graphs?

---