"Given a coding solution, explain its time complexity and space complexity. Describe how you derive the result and what operations dominate the overall cost."
Time complexity measures how the number of operations grows as input size increases. In interviews, the goal is usually to identify the dominant growth rate rather than count every instruction exactly.
for i in range(n):
total += nums[i] # O(n)
Space complexity measures the extra memory used by the algorithm, excluding the input unless stated otherwise. Interviewers usually care about auxiliary space such as hash maps, recursion stacks, queues, or temporary arrays.
seen = {}
for x in nums:
seen[x] = True # O(n) extra space
The final complexity is determined by the part of the algorithm that grows fastest with input size. Constant-time statements and lower-order terms are ignored in Big O notation.
for i in range(n):
pass
for i in range(n):
for j in range(n):
pass # Overall O(n^2)
Sequential loops usually add their costs, while nested loops multiply them. Distinguishing between these patterns is one of the fastest ways to analyze a solution correctly.
# Sequential: O(n) + O(n) = O(n)
# Nested: O(n) * O(n) = O(n^2)
Some operations are occasionally expensive but cheap on average across many calls. Dynamic arrays and hash tables often use amortized analysis, where average insertion remains O(1) despite occasional resizing.
arr.append(x) # Amortized O(1)
