Stating Time and Space Complexity
35 min · Intermediate
Every DSA answer ends with "what is the time and space complexity?". A strong answer gives both, names the dominant cost and its reason in one sentence, and does not miss hidden costs inside library calls.
Topics in this lesson
- Quick rules for loops, recursion and collection calls
- Hidden costs: substring, contains on a list, concatenation in loops
- Space: auxiliary vs output, and the recursion stack
- How to phrase it in the interview
Interview questions this lesson answers
- What does Big-O notation describe?
- How do you find the complexity of nested loops?
- What about loops one after another?
- When is a loop O(log n)?
- How do you find the time complexity of a recursive function?
- What is the space complexity of recursion?
- What is the difference between auxiliary space and total space?
- Do you count the output in space complexity?
- What are hidden costs in Java code?
- Why is string concatenation in a loop O(n²)?
Sign in free to continue this lesson
Create a free account to read every lesson, practise with the exercises and keep track of your progress.