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

```
1 def 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:

```
1 def 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