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:
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