Skip to content

Week 8: Algorithms, complexity, and your first practice problems

~9 min

This week's goal

This week you learn to estimate how much work a program does before you run it. You count steps in loops, write the count as a formula, and compare that count with a time limit. Then you apply the idea to five short practice problems from the CSES problem set. The practice matters more than the reading this week, so plan most of your time for the problems.

The main text is counting steps and choosing a Python interpreter from the Python course. The wider topic is covered in the data structures and algorithms page.

Day-by-day (about 1.5-2 hours per day)

Day 1. Read the first half of the complexity lesson, up to the discussion of sorting. The key idea is that a single loop over n items does n steps, which is O(n), and a loop inside a loop does about n * n steps, which is O(n^2). Write both examples in a file and count the steps for n = 10 on paper.

Day 2. Read the rest of the lesson, including the part on sorting and the note on PyPy. Look up the cost of common Python operations on the Python wiki's time complexity page. Two rows to note: x in list takes O(n), and x in set takes O(1) on average. Write a short test that shows the difference for a list of one million numbers, and time it with time.perf_counter.

Day 3. Start the first CSES problem, Weird Algorithm. Read the statement, write a simple version first, then test it on a few starting values. Submit the solution on the CSES site. Write one line in your notes that says how many steps your loop takes for the largest allowed input.

Day 4. Solve Missing Number and Increasing Array. For the first, a set or a formula works. For the second, think about the largest value seen so far as you go through the array. Before you submit, write the step count of your method in terms of n, and check whether it fits the limit that the statement gives.

Day 5. Solve Repetitions. Walk through your code by hand on the input ATTCGGGA, and write the value of each variable on each step. The answer should be 3. This habit, tracing by hand, catches many bugs that submissions do not explain well.

Day 6. Solve Bit Strings. The answer is a power of two, taken modulo a number that the statement gives. Think about why a loop of n multiplications is fine here but would be slow if n were much larger. Then open the OCW 6.006 course page and look at how the course frames the same questions about cost.

Day 7 is a rest day.

Deliverable

A file practice-week-08.py with a function for each of the five problems, a comment above each function that gives its step count, and a note that says whether the submission was accepted. If a problem is not accepted yet, keep it in the file with a note of what you tried. A rejected attempt is useful work.

Check yourself

  1. How many steps does a loop for i in range(n): total += i take, as a formula?
  2. Why is a loop inside a loop over the same n items usually O(n^2)?
  3. Why do you write the simple method first, even when you expect the fast method to be correct?
  4. What does a time limit tell you about the method you should use?
  5. Why is x in set usually faster than x in list for large collections?
Answers
  1. It takes n steps, because the loop body runs once for each value from 0 to n - 1. Its cost is O(n).
  2. The inner loop runs about n times for each of the n passes of the outer loop, which gives about n * n steps. The formula is n^2.
  3. The simple method is easy to check and gives you something to compare against on small inputs. If the fast method gives a different answer on a small case, the simple method usually shows which one is wrong.
  4. It tells you how many steps are safe. For n near 2 * 10^5, a method with n^2 steps is too slow, and a method with about n log n steps is fine.
  5. A set finds an item by hashing it, which takes about constant time on average. A list checks items one at a time, which takes time proportional to its length.

Sources