What is Time Complexity? How is it different from Space Complexity?
Time Complexity vs Space Complexity
Time Complexity measures how the running time of an algorithm grows as a function of the size of its input, typically expressed using asymptotic notation like Big-O. It does not measure actual wall-clock time (which depends on hardware), but rather the number of fundamental operations performed relative to input size n.
Space Complexity measures how much additional memory an algorithm requires as a function of input size, including auxiliary space used for variables, recursion stacks, or temporary data structures, in addition to the input itself. In interviews, 'space complexity' usually refers to auxiliary space, excluding the space needed for the input.
- 1
Time complexity: growth of number of operations vs input size
- 2
Space complexity: growth of memory usage vs input size
- 3
Both are typically expressed with Big-O, Big-Theta, or Big-Omega notation
- 4
There is often a time-space trade-off, e.g., memoization trades space for time
Scenario Questions
0-2 years experience
- 1Suppose you need to reverse a singly linked list. How would you evaluate the time and space complexity of your solution, and what would change if you used recursion instead of iteration?
- 2You have an array of 1 million integers and need to find the maximum value. What is the time and space complexity of a straightforward scan, and could you improve either?
- 3If you implement bubble sort on a list of 10 elements, what are its time and space complexities, and why might you still choose it in a junior project?
2-5 years experience
- 1Your team added a new caching layer to a service, but response latency increased unexpectedly. Walk me through how you would profile the time vs space trade‑offs to pinpoint the issue.
- 2During a code review, a colleague's depth‑first search uses recursion and crashes on large graphs. How does the space complexity affect this, and what alternatives could you propose?
- 3We need to sort up to 10 million user records. Explain how you would pick an algorithm based on time and space constraints, and what factors would influence your decision.
5-8 years experience
- 1Our search service processes billions of queries daily. Describe how you would balance the time complexity of query processing with memory usage for indexes, and what architectural patterns help you scale.
- 2A batch job that aggregates logs runs in O(n²) time and consumes a lot of heap memory, causing OOM errors. How would you refactor it to improve both time and space complexity while preserving business output?
- 3When migrating a legacy monolith to microservices, you must decide whether to keep intermediate results in‑memory or persist them. Discuss the trade‑offs in terms of time vs space complexity and operational impact.
8+ years experience
- 1Your organization is moving a platform to a cloud data warehouse. How would you evaluate long‑term time and space complexity implications of different partitioning and indexing strategies across teams?
- 2Multiple teams are adding large in‑memory caches for new features. As a staff engineer, how would you set guidelines to keep overall system memory within budget without hurting request latency?
- 3We need real‑time analytics on petabyte‑scale event streams. Propose an architecture that balances algorithmic time complexity with space constraints, considering cost, maintainability, and future growth.
Follow-up Questions
- What would change in your analysis if the input size doubled?
- How do you usually verify the theoretical complexity against real‑world measurements?
- Can you describe a case where you would prioritize space savings over faster runtime?