A girl and a robot thinking together

Let’s think it through · Start with a story

The robot recalculates the total pages read on the first three days each time. The girl writes down the combined total for the first two days.

Break down the process

Follow the numbered steps, then explain them in your own words
  1. First calculation2 + 3 = 5
  2. Save the resultFirst two days total 5
  3. Add a day5 + 4 = 9
  4. ReuseNo need to start over

After finding repeated subproblems, consider saving results that can be reused.

The key is to confirm that the same task has the same inputs and that its result will not become invalid because of changes in external state.

01What is repeated work?

It is when a program calculates the same result multiple times even though it already knows it or could have saved it.

For example, when answering many range-sum queries, adding each range from scratch can repeatedly calculate the same prefixes.

02How can you spot it?

Write out a few calculations:

Query 1: add a1+a2+a3+a4;Query 2: add a1+a2+a3 again

You can see that the earlier part appears repeatedly.

03How do prefix sums eliminate repeated work?

Save the totals in advance:

prefix[i] = a[1] + ... + a[i]

Then each range sum needs only the difference between two prefix values.

04Can recursion repeat work, too?

Yes. Consider the naive Fibonacci function:

fib(5)
├─ fib(4)
│  └─ fib(3)
└─ fib(3)

fib(3) is calculated multiple times.

Later, you can use memoization to save the results of subproblems that have already been calculated.

05Can repeated work always be eliminated?

Not all of it—and not always worth the effort.

Saving results requires extra memory and management, so consider how often the work repeats and how large the data is.

06Where else can you look for repetition?

Loops

Is the same expression recalculated every iteration?

Queries

Are you repeatedly scanning the same data range?

Search

Do you reach the same state more than once?

What you have learned

  • Repeated work is one important cause of slow programs.
  • Expanding a calculation by hand can help reveal repetition.
  • Prefix sums, caches, and memoization can reduce some repeated calculations.
  • Saving results also costs memory.
  • Before optimizing, confirm where the work actually repeats.

Next: How Do You Choose the Right Data Structure and Algorithm?

Your turn

If the first day’s page count changes from 2 to 6, can you still use the saved total of 5 for the first two days?

Have an answer? Click to see the explanation

No. The relevant data changed, so the accumulated total needs to be updated as well.