Time and Space Complexity Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the module: counting steps, growth rates, the real cost of Python operations and space. For each task, name the cost first, then write or fix the code.
Read code and name its cost
Complexity analysis is naming how the steps and the memory of a solution grow with n, so you can compare solutions and reject slow ones before you run them.
Look at the loops first. One pass is O(n), a loop inside a loop is O(n²), and halving is O(log n). Then look for hidden loops inside in, slices and count.
def first_big(orders, limit): for amount in orders: if amount > limit: return amount
def has_pair(orders, target): for a in orders: for b in orders: if a + b == target: return True return False
print(first_big([5, 80, 30], 50), has_pair([5, 80, 30], 35))Example 1 · Same job, two costs
def max_brute(values): steps = 0 for a in values: is_max = True for b in values: steps += 1 if b > a: is_max = False if is_max: return a, steps
def max_scan(values): best = values[0] steps = 0 for value in values: steps += 1 if value > best: best = value return best, steps
values = list(range(1, 201))print(max_brute(values))print(max_scan(values))(200, 40000) (200, 200)
What this code does
- The brute force compares every value with every other value: 200 * 200 = 40000 steps, O(n²).
- One scan keeps the best so far: 200 steps, O(n).
- The built-in
maxdoes the same single scan.
first_big makes one pass: O(n) time, O(1) space. has_pair has a loop inside a loop: O(n²) time, O(1) space.
Pick the structure that removes the loop
A repeated scan is usually the slow part. A set, a dict or a Counter turns "look through the list" into one lookup, at the price of O(n) extra space.
from collections import Counter
orders = [7, 3, 9, 3, 7, 7]counts = Counter(orders)print(counts.most_common(1))Example 2 · Customers per city
from collections import Counter
cities = ["Pune", "Delhi", "Pune", "Mumbai", "Delhi", "Pune"]counts = Counter(cities)for city, total in sorted(counts.items(), key=lambda pair: (-pair[1], pair[0])): print(city, total)Pune 3 Delhi 2 Mumbai 1
What this code does
- Counter counts in one pass: O(n) time and O(k) space for k different cities.
- Sorting only the k results costs O(k log k), which is tiny when k is small.
One pass builds the counts in O(n). Calling orders.count for each order would be O(n²).
Check the limit before you code
Read n, pick the growth rate that fits about 10⁷ steps, then write the simplest solution of that rate. Say the time and the space aloud when you finish.
n = 200_000print(n * n <= 10_000_000)print(n * n.bit_length() <= 10_000_000)Example 3 · Count pairs with a dictionary
from collections import Counter
def count_pairs(values, target): seen = Counter() pairs = 0 for value in values: pairs += seen[target - value] seen[value] += 1 return pairs
print(count_pairs([1, 5, 3, 3, 7, 5, 1], 8))6
What this code does
- For each value,
seen[target - value]is how many earlier values complete the pair. - One pass, O(n) time and O(n) space, against O(n²) for checking every pair.
The first line is False: a loop inside a loop is too slow. The second is True: sorting or a single pass with a dict fits.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Count how many times the inner body runs for for i in range(8): for j in range(i + 1, 8). Print the count.
28
Exercise 2· Easy
Remove the duplicates from [3, 1, 3, 2, 1], keeping the first-seen order, using a set. Print the list.
[3, 1, 2]
Exercise 3· Medium
Find the first customer id that appears twice in [4, 9, 2, 9, 4] using a set. Print it.
9
Exercise 4· Medium
Count the pairs (i, j) with i < j whose values add up to 6 in [2, 4, 6, 2, 4], in one pass with a Counter. Print the count.
4
Exercise 5· Medium
Write triangular(n) with a loop (not recursion) that returns 1 + 2 + ... + n. Print triangular(200000).
20000100000
Exercise 6· Hard
For values = [4, 1, 7, 3, 9], build a prefix-sum list once, then answer two inclusive range sums: positions 1 to 3 and positions 0 to 4. Print the two answers on separate lines.
11 24
Exercise 7· Hard
Find the largest sum of 3 consecutive values in [2, 1, 5, 1, 3, 2] with a sliding window that adds the new value and subtracts the one that leaves. Print it.
9
Exercise 8· Hard
A list has 1000 values. Count the steps for 500 range-sum queries over the whole list done two ways: adding up each range (brute force) and a prefix-sum build plus one step per query. Print the two counts as brute prefix.
500000 1500
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Time and Space Complexity