Algorithm analysis is a core interview skill because it shows whether you can reason about scalability before optimizing code. Interviewers want to see that you can estimate runtime, memory usage, and pinpoint the operation that dominates performance.
Explain how you would calculate time complexity and space complexity for an algorithm, and how you would identify its bottleneck.
Address these sub-questions:
Give a practical interview-style explanation rather than a formal proof. You should define the concepts, walk through how to analyze code step by step, and use small code examples to show how bottlenecks are identified.
Big-O describes how runtime or memory grows as input size increases. In interviews, it is used to focus on the dominant growth rate rather than exact instruction counts.
for i in range(n):
print(i) # O(n) time
When combining multiple parts of an algorithm, the largest-growing term determines the overall complexity. Constants and lower-order terms are ignored because they matter less as input size becomes large.
O(n) + O(n^2) = O(n^2)
Space complexity measures extra memory used by the algorithm, excluding the input unless stated otherwise. Temporary arrays, hash maps, recursion stacks, and queues all contribute to auxiliary space.
seen = set() # up to O(n) extra space
A bottleneck is the part of the algorithm that dominates runtime or memory usage. It is usually the most expensive repeated operation, such as a nested loop, sort, or large auxiliary structure.
nums.sort() # O(n log n), often dominates linear passes
Some operations are usually fast but occasionally expensive, such as dynamic array resizing or hash table rehashing. Interviewers often expect you to mention whether your complexity is worst-case, average-case, or amortized.
arr.append(x) # amortized O(1)
