0
def allFib(n):
 for i in range(n):
   print(str(i) + ":, "+ str(fib(i))

def fib(n):
  if n<=0:
    return 0 
  elif n == 1:
    return 1 
  return fib(n-1) + fib(n-2)

Shouldn't fib being called N time be accounted here?

noob master69
  • 3
  • 1
  • 1) The time complexity is not 2^n, but rather phi^n where phi is the golden ratio; 2) The formula for the sum of a [geometric progression](https://en.wikipedia.org/wiki/Geometric_progression) shows that the sum for i = 0 to n is proportional to phi^n, not n * phi^n. – kaya3 Sep 13 '22 at 15:45
  • @JRose It's not a solution to the recurrence relation. It's an upper bound for a solution. To say that a loose upper bound is "the" time complexity is at best misleading, and suggestive of a misconception. – kaya3 Sep 13 '22 at 15:52
  • See [Is the running time of this double loop O(n2^n) or O(2^n)?](https://stackoverflow.com/questions/38965698/is-the-running-time-of-this-double-loop-on2n-or-o2n) and [Computational complexity of Fibonacci Sequence](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence). – kaya3 Sep 13 '22 at 15:58

0 Answers0