Let's consider the complexity of fact(n)
def fact(n):
if n == 0:
return 1
return n*fact(n-1)
Excluding the times the recursive calls take, each call to fact(n) takes the same amount of time, assuming that n is a float.
(Note: that's because multiplication of floats is a constant-time operation, regardless of the magnitude of the float, since floats each have the same number of digits. This is not the case with Python 3 ints)
For fact(n), we can simply count the number of calls we need to complete the computation of fact(n):
0
|
1
.
.
.
|
n-2
|
n-1
|
n
As is apparent from the call tree, we need $n+1$ calls in total to compute fact(n), so that the runtime of fact(n) is proportional to n+1. That means the runtime complexity of fact(n) is $`\mathcal{O}(n)`$. (If n is a float, again.)
We could easily make fact(n) slower:
def slow_mult(n, m):
'''Return n*m
Arugments:
n, m - floats that are non-negative whole numbers
'''
s = 0
for i in range(int(n)):
s += m
return s
def fact_slow(n):
if n == 0:
return 1
return slow_mult(n, fact_slow(n-1))
slow_mult(n, m) runs in time proportional to n -- it takes approximate k\times n time, where k is the amount of time it takes to perform one iteration of the loop in slow_mult().
We can now figure out the total number of time that fact_slow() takes by summing up how much each call takes:
call time needed
0 0
|
1 k*1
.
.
.
|
n-2 k*(n-2)
|
n-1 k*(n-1)
|
n k*n
The total amount of time needed is
$k(1+2+3+4+5+....+n) = k\sum_{i=1}^n i = k n(n+1)/2$, which is $\mathcal{O}(n^2)$
In simple cases, it's enough to count the number of recrusive calls to figure out the complexity. But that only works if each call takes the same amount of time (not counting recursive calls). If different calls take different amounts of time, this are more complicated.