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