At companies like Stripe, interviewers often ask you to justify not only that a solution works, but also how efficient it is. Clear time complexity analysis shows that you understand the algorithm beyond the code.
Explain the time complexity of your solution for a specific coding problem.
Address these points:
Give a practical interview-level explanation. You should be able to walk through a concrete solution, identify the dominant operations, simplify the expression using Big-O notation, and briefly mention space complexity if it materially affects the design.
Big-O describes how runtime grows as input size increases. In interviews, it is used to communicate the upper bound of growth while ignoring constants and lower-order terms.
for i in range(n):
print(i) # O(n)
To analyze runtime, identify the operation that executes most often as input grows. Even if a solution has several parts, the slowest-growing term dominates the final complexity.
for i in range(n):
pass
for j in range(n * n):
pass # Overall O(n^2)
Sequential loops usually add their costs, while nested loops multiply them. This distinction is one of the most common sources of mistakes in interview complexity analysis.
for i in range(n):
for j in range(n):
pass # O(n^2)
The cost of lookups, insertions, and deletions depends on the data structure. For example, array scans are often O(n), while hash table lookups are typically O(1) average case.
seen = {}
for x in nums:
if x in seen: # average O(1)
return True
seen[x] = True
Some operations have different complexity depending on the scenario. A strong answer mentions which case applies and why, especially for hash tables, dynamic arrays, and recursive algorithms.
arr.append(x) # amortized O(1)
