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:
Time taken by all calls:
Solving the recurrence relation
Since then and
Generalising for k:
Which leads us back to the same result as when analysing the call tree: