recurrence relation with for loop
We began with a recurrence relation for a simple decreasing function, now let's build on it, by adding a for loop.
1def func(n):
2 if n > 0:
3 for i in range(n):
4 print(i)
5 test(n-1)
Building our recurrence relation
Let's step through and assign how many units of work need to be carried out for each statement in our function.
1def func(n):
2 if n > 0: # 1
3 for i in range(n): # n
4 print(i) # n
5 func(n-1) # T(n - 1)
So our recurrence relation is:
Since this is asymptotic analysis, we are allowed to drop constants to make our work easier, so for the purpose of solving this, we'll make it:
As a piecewise function:
Solving the recurrence relation using the call tree
Now looking at our call graph, we can quite clearly deduct the time complexity:
graph TD
5[func 5] -->|print| 5p0[0]
5[func 5] -->|print| 5p1[1]
5[func 5] -->|print| 5p2[2]
5[func 5] -->|print| 5p3[3]
5[func 5] -->|print| 5p4[4]
5[func 5] -->|call| 4[func 4]
4[func 4] -->|print| 4p0[0]
4[func 4] -->|print| 4p1[1]
4[func 4] -->|print| 4p2[2]
4[func 4] -->|print| 4p3[3]
4[func 4] -->|call| 3[func 3]
3[func 3] -->|print| 3p0[0]
3[func 3] -->|print| 3p1[1]
3[func 3] -->|print| 3p2[2]
3[func 3] -->|call| 2[func 2]
2[func 2] -->|print| 2p0[0]
2[func 2] -->|print| 2p1[1]
2[func 2] -->|call| 1[func 1]
1[func 1] -->|print| 1p0[0]
1[func 1] -->|call| 0[func 0]
Time taken by all calls:
So
i.e
Solving the recurrence relation
Since then and
Substituting back
Resulting in
Substituting again
Generalising for k:
Assume: therefore
Which leads us back to the same result as when analysing the call tree:
i.e