Java Complexity analysis
The vocabulary the rest of the round is conducted in. Getting this wrong makes every later answer sound uncertain.
2 concepts · 6 interview questions
What this topic covers
Every concept in complexity analysis, and the questions each one gets asked as. Where a question links, it has a full write-up.
Time and space complexity
An upper bound on growth as input size increases, ignoring constants. It describes scaling behaviour, not speed at a particular size.
- What is the time complexity of your solution?
- When is an O(n log n) solution slower than an O(n squared) one?
- What does amortised complexity mean?
Trading space for time
Most interview optimisations are the same move: store something you already computed so you do not compute it again.
- How would you make this faster if memory were free?
- Does recursion cost space, and how much?
- What is the space complexity of your sort?