I'm struggling with finding out the operation time of when n is 10,000 in this recursive function:
def fib3(n):
if n<3:
return 1
else:
return fib3(n-1) + fib3(n-2) + fib3(n-3)
I understand in loops it is straightforward to say what the running time is - it is the number of loops, but how do we do this in recursion?
If you instrument your code like this
from collections import Counter
c = Counter()
def fib3(n):
c[n] += 1
if n < 9980:
return 1
else:
return fib3(n-1) + fib3(n-2) + fib3(n-3)
fib3(10000)
print c
You'll get a result like this
Counter({9979: 223317, 9978: 187427, 9977: 121415, 9980: 121415, 9981: 66012, 9982: 35890, 9983: 19513, 9984: 10609, 9985: 5768, 9986: 3136, 9987: 1705, 9988: 927, 9989: 504, 9990: 274, 9991: 149, 9992: 81, 9993: 44, 9994: 24, 9995: 13, 9996: 7, 9997: 4, 9998: 2, 9999: 1, 10000: 1})
Ignoring the values for keys less than 9980, you can already see that the number of calls approximately doubles for each n as n decreases
So you can estimate that the complexity as O(2n) (It's actually about O(1.839n))
If you wish to calculate the exact number of calls, you should try writing a recursive function, say fib3_count(n) that returns the number of calls required to calculate fib3(n)
EDIT:
Calculating the big-O complexity can be done by solving this equation
x**3 - x**2 - x**1 - 1 == 0
Where the complexity is O(xn)
The 3 roots to the equation are
x1 = 1.8392867552141612
x2 = (-0.41964337760708065+0.6062907292071992j)
x3 = (-0.41964337760708065-0.6062907292071992j)
Since x has to be real, we are left with: O(1.8392867552141612n)
O(2^n) matches the answer. On each recursive call it has 3 sub calls, so it should be O(3^n).This runs in exponential time. It's straightforward to show that fib3(i) runs quicker than fib3(k) if i < k, since computing fib3(k) will involve computing fib3(i), possibly many times. Computing fib3(n+3) requires computing fib3(n+2), fib3(n+1), and fib3(n); thus, it takes at least 3 times as long as computing fib3(n). By induction, you can show that fib3(n) takes at least O(3^(n/3)) time to compute. A more sophisticated analysis could give an asymptotically exact bound.
3^n is not proportional to 3^(n/3); the ratio between those functions is 3^(2n/3).On each recursive call you do 3 additional calls. It's very similar to the binary tree, but there they have 2 children and the total number of children in full binary tree is pow(2, n).
Here you have 3 diversions of flow, which makes it O(3^n)
EDIT:
Here is some code:
import math
class F:
def __init__(self):
self.c = 0
def fib3(self, n):
self.c += 1
if n < 3:
return 1
else:
return self.fib3(n-1) + self.fib3(n-2) + self.fib3(n-3)
f = F()
f.fib3(20)
print f.c
the output will be:
128287
print math.pow(3, 20) evaluates to 3486784401. Which is overestimate, but it's dictated by the fact that fib3 can decreases by 3 instead of 1.
if you run the following code with fib3 always called on n-1 you will get O(3^n)
import math
class F:
def __init__(self):
self.c = 0
def fib3(self, n):
if n < 1:
return 1
else:
self.c += 1
return self.fib3(n-1) + self.fib3(n-1) + self.fib3(n-1)
f = F()
f.fib3(10)
print f.c
Actually you will get O((3^n) / 2), but two here is a factor, so it will be just O(3^n)
n. However, many paths are shorter than n, some as short as about n/3. You can see a similar effect in the runtime of the naive recursive method of computing the fibonacci sequence; the runtime of that is O(phi^n), where phi is the golden ratio, despite all non-leaf calls producing 2 recursive calls.3^n and 3^(n/3) do not differ by a constant factor. They differ by an exponential factor, 3^(2n/3). Big-O notation does not drop such factors.
niterations runs inO(n)time if the runtime of each iteration is bounded by a constant, but if the per-iteration runtime is not bounded in such a fashion, the loop may run in time much worse thanO(n).