Say it before you code
Announcing "this will be O(n log n) time and O(n) space" before writing anything is a strong habit. It shows you have a plan, and it invites a correction if the interviewer wanted something better.
The common ones
- Hash map insert and lookup: O(1) average, O(n) worst case on adversarial collisions.
- Sorting: O(n log n).
- Binary search: O(log n).
- Heap push and pop: O(log n); building a heap from an array is O(n), which surprises people.
- Traversing a graph: O(V + E).
Amortised versus worst case
Appending to a dynamic array is amortised O(1): most appends are cheap, occasional ones reallocate and copy everything. Average constant, worst case linear.
That distinction matters in latency-sensitive systems, where the occasional slow operation is exactly what you care about. A trading system may prefer a predictable O(log n) to an amortised O(1) with a bad tail.
Making that point unprompted is a genuinely good signal.
Space complexity
Frequently forgotten. Remember:
- The recursion stack counts. A recursive traversal of a skewed tree is O(n) space.
- Output space is sometimes counted, sometimes not - ask.
- In-place algorithms are O(1) auxiliary space, which is often what "space efficient" means.
Constants matter more than you think
At realistic problem sizes, an O(n log n) algorithm with good cache behaviour routinely beats an O(n) algorithm that chases pointers. Asymptotics describe the limit, and you may never reach it.
For quant systems processing bounded, known-size data, the constant factor is frequently the entire story - see C++ for low latency.
The follow-up to expect
"Can you do better?" Usually yes, and usually by trading space for time - a hash map to avoid a nested loop is the archetype. If you genuinely cannot, saying why there is a lower bound is a strong answer.
Practise in programming and DSA.