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 measures how the number of operations grows, while space complexity measures how much extra memory grows.
- A solution can be fast but memory hungry, or slow but memory light, so the two are often traded against each other.
- A hash set is the classic trade, using O(n) extra space to cut time from O(n squared) to O(n).
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
int total = 0;
for (int x : nums)
total += x;
// O(n) time, O(n) extra space
unordered_set<int> seen;
for (int x : nums)
seen.insert(x);// O(n) time, O(1) extra space
int total = 0;
for (int x : nums)
total += x;
// O(n) time, O(n) extra space
Set<Integer> seen = new HashSet<>();
for (int x : nums)
seen.add(x);# 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).
Frequently asked questions
Does recursion use extra space?
Yes. Each recursive call adds a frame to the call stack, so recursion depth of n uses O(n) extra space even if it uses no other data.
What does O(1) extra space mean?
It means the algorithm uses a fixed amount of extra memory no matter how large the input is, such as a few counter variables rather than a new list.
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