What is the difference between time and space complexity?
Time complexity measures how the number of operations grows as the input grows, so it is about speed. Space complexity measures how much extra memory an algorithm needs as the input grows, so it is about memory. A solution can be fast but memory hungry, or slow but memory light, and interviewers often want you to discuss the trade off.
Time complexity
This counts how many steps the algorithm takes relative to the input size. A single loop over n items is O(n) time because the number of steps grows with n.
Space complexity
This counts the extra memory the algorithm uses beyond the input. If you copy all n items into a new list you use O(n) extra space. If you only use a few variables you use O(1) extra space.
# O(n) time, O(1) extra space
total = 0
for x in nums:
total += x
# O(n) time, O(n) extra space
seen = set()
for x in nums:
seen.add(x)When asked to optimise, first ask whether they care more about time or memory. Many problems have a clean answer where you trade extra memory, such as a hash set, to cut the time from O(n squared) to O(n).
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions