Analyze time and space complexity
Describe how running time and memory grow with input size.
- Describe algorithms with Big O notation.
- Recognize common complexity classes.
- Trade memory for speed deliberately.
Big O describes how an algorithm’s cost grows as the input size n grows, ignoring constant factors. Interviewers expect you to state the time and space complexity of every solution you propose, and to explain why. It is also how you know whether a solution is fast enough: with n = 100,000, an O(n²) algorithm does 10 billion steps; an O(n log n) one does about 1.7 million.
Common complexity classes
- O(1) constant: indexing a list, a dict lookup (on average).
- O(log n) logarithmic: binary search - the problem halves each step.
- O(n) linear: one pass over the input.
- O(n log n): efficient sorting.
- O(n²) quadratic: nested loops over the input.
- O(2ⁿ) exponential: trying every subset.
Space complexity counts extra memory. Many optimizations trade space for time: storing what you have seen in a set turns repeated O(n) scans into O(1) lookups.
1nums = [4, 1, 7, 1]
2
3# O(n^2) time, O(1) space: compare every pair
4pairs = any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, len(nums)))
5
6# O(n) time, O(n) space: remember what we have seen
7seen, found = set(), False
8for num in nums:
9 if num in seen:
10 found = True
11 seen.add(num)
12
13print(pairs, found)True True
When you analyze code, count the loops and what happens inside them. A loop over n items that does an O(1) dict lookup is O(n). A loop that calls list.index or x in some_list inside it is hiding a second O(n) loop, making the whole thing O(n²). Drop constants and lower-order terms: O(2n + 5) is O(n).
Key takeaways
Big O describes growth, ignoring constants and smaller terms.
Nested loops over the input usually mean O(n²).
Hash sets and maps trade O(n) memory for O(1) average lookups.
Lesson quiz
6 questions · pass with 5 correct · up to 50 XP
Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.
Practice: solve interview problems
Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.
Detect duplicates in O(n)
Read a line of space-separated integers. Print true if any value appears more than once, otherwise false. Aim for O(n) time using a set.
- Has a duplicate
- All distinct
Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.
Questions about this lesson
Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.
Loading posts…