Remembering answers fib has already worked out
Computed by plain recursion, fib(30) makes 2,692,537 calls, and fib(40) takes about 6 seconds to add up numbers that a loop adds in 40 steps. This lesson starts by finding where those calls go and removing the wasted ones. Then it turns to a question several lessons have touched already: how to tell, before you run a program, whether it will be fast enough.
Most of fib's calls redo work that has already been done. calls and , but calls as well, so is worked out twice and three times. can only ask 31 different questions, up to , so the other 2.69 million calls each ask one of them again. If each answer is written down the first time it is worked out, a repeated call can look it up instead.
Step through the call tree for with the memo off, and count how often is worked out. Then switch the memo on and step through again.
With the memo off, makes 15 calls and works out three times. With the memo on, it makes 9: to are each worked out once, and every repeat is answered from the memo without further calls.
Definition
Memoization
Memoization saves each call's result in a table, the memo, keyed by the argument. A call checks the memo first and returns a saved answer at once.
Fibonacci with a memo
Here is fib with a memo, a dictionary that maps each to . The memo is created once, outside the function, so every call reads and writes the same one. A second global name, calls, counts the calls.
memo = {}
calls = 0
def fib(n):
global calls
calls += 1
if n in memo:
return memo[n]
if n < 2:
result = n
else:
result = fib(n - 1) + fib(n - 2)
memo[n] = result
return result
print(fib(30))
print(calls)Python details
global calls lets fib change the global name calls, the way nonlocal lets a function change a name in an enclosing frame. Without it, calls += 1 looks for calls in the call's own frame and stops with an UnboundLocalError.
The answer is still 832,040, and the calls drop from 2,692,537 to 59. Delete the memo check at the top of fib and the same program prints 2,692,537 again. Here is where the 59 comes from. The first call is , each of to is worked out once and makes two calls, and every other call is a lookup or a base case that makes none:
In general, memoized makes calls. , about , takes 179.
The memo costs memory in return: one saved answer for each different argument, 31 of them for .
The cost of a memoized recursion
The count of 59 follows a rule that holds for any memoized function. Each different argument is worked out once and every repeat costs one lookup, so the work is about the number of different arguments times the work one call does itself. To estimate a memoized recursion, count the different arguments it can be called with. In the next problem, that count decides whether a memo is enough.
A function on non-negative integers has and for every positive integer , where rounds down to an integer. Given , print .
Constraints
Sample 1 · Input
2
Output
3
Sample 2 · Input
0
Output
1
Sample 3 · Input
100
Output
55
In the first sample, , so . Written as a plain recursive function, the definition is far too slow. Every branch of its calls ends at , which adds 1 to the answer, so the plain recursion makes about twice as many calls as its answer. For the answer is about , so that is about calls.
This lesson's estimates use a rough figure for C++, simple steps a second; a Python program takes about ten times as long. For the plain recursion:
With a memo, what matters is how many different come up. Every is divided by 2 and by 3 some number of times, rounding down each time, and neither the order nor the rounding changes the result: , the same as dividing by 6 once. So every is divided by some and rounded down. Since and both exceed , stays below 60 and below 38 while is above 0, which allows at most values above 0. For only 1,011 of them come up.
memo = {}
def f(k):
if k == 0:
return 1
if k in memo:
return memo[k]
memo[k] = f(k // 2) + f(k // 3)
return memo[k]
n = int(input())
print(f(n))For this program makes 2,023 calls: the first one, plus two for each of the 1,011 values it works out. Each call at least halves , so no more than about 60 calls are open at once.
The next problem is practice for counting arguments.
A blackboard holds one integer . While some integer is on the board, Takahashi erases one occurrence of it, writes and , and pays yen. The total is the same in whatever order he picks the numbers. Print the total he pays.
Constraints
Sample 1 · Input
3
Output
5
Sample 2 · Input
340
Output
2888
Sample 3 · Input
100000000000000000
Output
5655884811924144128
For 3, he pays 3 and the board holds 1 and 2; then he pays 2 and the board holds three 1s, so the total is 5. Simulating the board takes at least steps, because it ends with ones. Instead, write what erasing eventually costs as a recursive function of , and count its different arguments before you trust a memo with .
Deeper read: memo containers and the depth limit
Python can keep the memo for you. Write @cache, imported with from functools import cache, on the line above def fib(n):, and Python saves each result keyed by the arguments, as the dictionary did. The results live in a dictionary, so a list argument stops it with a TypeError: a list cannot be a dictionary key.
A memo removes repeated calls but leaves the chain of open calls as long as before: memoized is 5,000 frames deep, past the recursion limit of 1,000, and stops with a RecursionError.
The fix is to fill the memo in a loop from the smallest argument up, so every value a call needs is already there. Filling a table from small cases to large is the start of dynamic programming, which the DSA roadmap teaches.
Orders of growth: constant and linear work
The memo did more than make faster: it changed how the work grows as grows. Without the memo, each step from to multiplies the calls by about 1.6, so every 5 steps multiply them by about 11. Work that is multiplied by a fixed factor each time grows by 1 is exponential, like the subsets of elements. With the memo, each step adds 2 calls, so the calls grow in proportion to . Work that grows in proportion to is linear.
The way a program's work grows with the size of its input is its order of growth, and for large inputs it decides which of two programs finishes first. You have met several orders already without names: the pair loop, selection sort, the library sort and the halving loop. The rest of this lesson names them, so that you can compare two ideas for a problem before you write either.
The simplest comparison is the sum . A loop adds each number in turn. A formula gives it at once: pairing the first number with the last, the second with the second-to-last, and so on gives pairs that each add up to , so the sum is . This program computes it both ways for .
n = 1000000
total = 0
for i in range(1, n + 1):
total += i
print(total)
print(n * (n + 1) // 2)Both lines print 500,000,500,000. The loop body runs once for each number from 1 to , so the loop is linear: doubling doubles the work. The formula does one multiplication, one addition and one division whether is 10 or , so its work is constant: the same for every .
For a million numbers the loop's steps take a fraction of a second, so the formula only matters when is far larger, as in the next problem.
For a positive integer , let . Given , print .
Constraints
Sample 1 · Input
4
Output
2
Sample 2 · Input
5
Output
-3
In the samples, , and adds to get . A loop over every term is too slow for the largest :
An alternating sum in constant time
Pairing the terms gives a constant-time formula. The terms group as , and each pair adds up to 1. When is even there are pairs, so . When is odd there are pairs and one leftover term, :
n = int(input())
if n % 2 == 0:
print(n // 2)
else:
print(-((n + 1) // 2))Logarithmic work: halving until 1
Some work grows with , but far more slowly than linear work. Here is a halving loop: it counts how many times can be halved before it reaches 1, where each halving rounds down. Guess the count for , then step through it.
For the loop runs 9 times: 1,000, 500, 250, 125, 62, 31, 15, 7, 3 and then 1. For it runs 4 times, and for not at all. The number of passes is about , the exponent for which . Work that grows like is logarithmic.
Doubling adds one pass, so even needs fewer than 60:
Any program that cuts its problem in half at each step does logarithmic work. Binary search, in the DSA roadmap, finds a value among a million sorted elements in about 20 comparisons this way.
Fast powers by halving the exponent
Halving also speeds up a recursion. Computing a power by , with , makes one call for each exponent down to 0, so its work is linear in . When is even, instead: one call for half the exponent, and its result multiplied by itself. When is odd, the call uses and multiplies by one more . Each call halves , like the loop above.
This program counts the calls of both versions for . That power has 792 digits, and problems with powers this large usually ask for a remainder, so both versions keep only the last three digits, with % 1000 after each multiplication. The last three digits of a product depend only on the last three digits of its factors, so this gives the same digits as taking the remainder once at the end.
calls = 0
def power(b, n):
global calls
calls += 1
if n == 0:
return 1
return b * power(b, n - 1) % 1000
def fast_power(b, n):
global calls
calls += 1
if n == 0:
return 1
half = fast_power(b, n // 2)
if n % 2 == 0:
return half * half % 1000
return half * half * b % 1000
print(power(7, 937), calls)
calls = 0
print(fast_power(7, 937), calls)Both print 207. The plain version makes 938 calls, one for each exponent from 937 down to 0. The fast version follows : 11 calls, because halvings take 937 to 1, plus the calls for 1 and 0. For an exponent of , the plain version would need calls and the fast one about 61.
The depth differs as much. The plain version has 938 frames open at its deepest, close to the recursion limit of 1,000, and power(7, 1000) stops with a RecursionError. The fast version needs 11.
Square-root work: divisors in pairs
Between logarithmic and linear work sits a loop that stops at . To list the divisors of , you could try every from 1 to . But divisors come in pairs: when divides , so does , and the smaller of the two is at most . So a loop can try only while and print both divisors of each pair it finds.
n = 36
d = 1
while d * d <= n:
if n % d == 0:
print(d, n // d)
d += 1The loop tries to 6, six passes instead of 36, and finds every divisor of 36; 6 pairs with itself because . This is square-root work, and it grows faster than logarithmic work and far slower than linear work. For , where a loop up to needs 116 days:
The same loop checks whether is prime, because a number above 1 that has no divisor from 2 to has none between and either.
Quadratic work and the cost of sorting
Two more orders come from lessons you have done. A loop inside a loop multiplies the two pass counts: the pair loop checked pairs, and multiplying by 10 multiplied its work by 100. Work that grows like is quadratic. The library sort does about comparisons, an order called n log n. It is only a little more than linear work, because stays below about 20 for a million items.
Both orders give a correct answer to the next problem, but its constraints leave time for only one.
Given a sequence of integers , print YES if its elements are pairwise distinct, and NO otherwise.
Constraints
Sample 1 · Input
5 2 6 1 4 5
Output
YES
Sample 2 · Input
6 4 1 3 1 6 2
Output
NO
Sample 3 · Input
2 10000000 10000000
Output
NO
In the second sample, the second and fourth elements are both 1, so the answer is NO. Comparing every pair is quadratic, and too slow for :
Sorting first puts equal values next to each other: 4 1 3 1 6 2 becomes 1 1 2 3 4 6. After that, each element only needs comparing with the one before it.
n = int(input())
a = list(map(int, input().split()))
a.sort()
answer = "YES"
for i in range(1, n):
if a[i] == a[i - 1]:
answer = "NO"
print(answer)The sort does about comparisons and the scan after it more, so the program finishes in a fraction of a second where the pair loop needs 200.
A set gives a third way: put the numbers in a set and compare its size with . Each insertion takes a few steps on average, so this way is linear.
The orders of growth side by side
Here are the seven orders this lesson named, with the step count of each at three sizes of :
| Order | Example | |||
|---|---|---|---|---|
| constant, | the sum formula | 1 | 1 | 1 |
| logarithmic, | halving to 1 | 3 | 10 | 20 |
| square root, | divisors up to | 3 | 32 | 1,000 |
| linear, | the sum loop | 10 | 1,000 | |
| n log n, | sorting | 33 | 9,966 | |
| quadratic, | every pair | 100 | ||
| exponential, | every subset | 1,024 |
At every order is fast, which is why a program that passes the samples can still be too slow on the judge. At steps a second, the last column becomes:
A faster machine changes the time by a constant factor, while a better order changes it by a factor that grows with . On a machine ten times faster, the quadratic program still needs 17 minutes for ; the n log n program on the slower machine needs a fifth of a second.
Deeper read: constant factors and smaller terms
Each pass of the sum loop does an addition, a comparison and an increment, and the loop is still called linear: whether a pass takes one step or three, the work doubles when doubles. A program doing steps is slower than one doing steps only while . Past that point the quadratic one falls further behind as grows.
Smaller terms are dropped for the same reason. The pair loop does steps, and for large the is tiny beside , so the loop is quadratic. The base of a logarithm does not matter either: is always about 3.32 times , a constant factor.
Time complexity, the DSA roadmap's first topic, writes orders of growth in Big O notation, where the sum loop is and the pair loop is , and lists the input limits each order fits within a second.
Common mistakes
Estimating the work from the sample instead of the constraints.
- Where it breaks
- Comparing every pair in Distinct or Not passes all three samples instantly, since the largest has . On the judge, gives about comparisons, which take about 200 seconds at a second.
- The fix
- Put the largest from the constraints into the estimate before writing code, and sort then scan.
Creating the memo inside the function, as
memo = {}on the first line offib.- Where it breaks
- Every call gets a new, empty memo in its own frame, so no saved answer is ever found.
fib(30)still makes 2,692,537 calls, andfib(50)makes about , 400 seconds at calls a second. - The fix
- Create the memo once, outside the function, so every call reads and writes the same one.
Using
intin C++ for the argument and the memo in the problem Recursive?- Where it breaks
- An
intholds at most 2,147,483,647, so reading into one fails:cinstores 2,147,483,647, the largestint, and the program computes . - The fix
- Use
long longfor the argument, the answer and the memo:map<long long, long long>.
Recall A quadratic program takes 0.01 seconds for $n = 1{,}000$. About how long will it take for $n = 10{,}000$?
About 1 second. Multiplying by 10 multiplies by 100, and .
Recall Why does memoized $\text{fib}(30)$ make 59 calls instead of 2,692,537?
Only 31 different arguments occur. Each of to is worked out once and makes two calls, and every repeat is a lookup: .
Key terms
| Term | Meaning |
|---|---|
| memoization | Saving each call's result to reuse on a repeat call. |
| memo | The table that holds the saved results. |
| order of growth | How work grows with input size. |
| constant | The same work for every input. |
| logarithmic | One more step each time doubles. |
| square root | Work like , such as checking divisors up to . |
| linear | Work proportional to . |
| n log n | Work like , the cost of sorting. |
| quadratic | Work like , such as checking every pair. |
| exponential | Work multiplied by a fixed factor each time grows by 1. |
