recurrence relation for a simple decreasing function

← 🏠

Let's explore how to express a recurrence relation for a simple decreasing function and evaluate it using the substitution method. We'll analyse this piece of code:

1def func(n):
2  if n > 0:
3      print(n)
4      test(n-1)

This is the function's call graph:

graph TD 3[func 3] -->|print| 3p[3] 3[func 3] -->|call| 2[func 2] 2[func 2] -->|print| 2p[2] 2[func 2] -->|call| 1[func 1] 1[func 1] -->|print| 1p[1] 1[func 1] -->|call| 0[func 0]

Notice func gets called n+1 times. print gets called n times. So the total number of pieces of work being done is 2n+1, or in big oh notation O(n).

Let's find our recurrence relation:

1def func(n):
2  if n > 0:
3      print(n)     # unit of time: 1 
4      test(n-1)    # unit of time: T(n-1)

So total time:

You may be wondering why we didn't include the if n > 0 and we could. But the recurrence relation would still be: T(n) = T(n-1) + 1, because our constant work simply gets counted as the 1. We could also use a or c.

Let's rewrite our recurrence relation as a piecewise function:

So we know what T(n) is, it is T(n) = T(n-1) + 1. But what is T(n-1)? We need to solve it by substitution.

since:
therefore:
therefore:

Now we can substitute back into our original equation:



As well as:

At this point, this proof is tugging at the leash for its general form of:

Now let's assume that: which also implies that , therefore meaning that , and if you remember from our piecewise function

when n = 0 we get a 1, thus

or

See also:

generating callgraphs in python with mermaid
recurrence relation with for loop