2

Possible Duplicate:
Computational complexity of Fibonacci Sequence

Hi, I found out a inductive proof yesterday for the time complexity of a recursive Fibonacci program.The proof first claimed that the complexity is exponential(and later goes on to prove it by induction) by saying that:

There exists a "r" such that f(n) >= r^n for all r>=1 and n>=1.

Then it chooses r to be equal to 1+sqrt(5)/2 such that it satisfies the equation r^2 = r + 1.

(It later justifies it's choice for r).

And then it says that now the statement becomes f(n) >= r^(n-2).

I didn't understand this part how does it become r^(n-2) from r^n.Can someone please help me with that.

Community
  • 1
  • 1
station
  • 6,715
  • 14
  • 55
  • 89

2 Answers2

3

As Daniel says, r is greater than 1 so r^n is greater than r^(n-1) which is greater than r^(n-2) etc...

So you have indeed: f(n) >= r^n >= r^(n-1) >= r^(n-2)

Emmanuel
  • 13,935
  • 12
  • 50
  • 72
2
  • f(n) >= r^n
  • r * r * f(n) >= r^n (since r > 1)
  • f(n) >= r^(n-2)

I don't see how this relates to time complexity, though..? It sounds more like a discussion leading up to Binet's formula.

Daniel Lubarov
  • 7,796
  • 1
  • 37
  • 56
  • It shows that `f(n)` is `Ω(r^n)` by showing that `f(n) >= r^n` for some _r_ and sufficiently large _n_. – hammar May 03 '11 at 07:06
  • @hammer I see, it just seems like a funny approach. In my mind, the natural argument is this: `f(n) = 2*f(n-2)` is trivially exponential (given `f(1) = 1`) since it doubles every two steps, and `f(n-1) + f(n-2) > 2*f(n-2)` since `f` increases monotonically, hence `f(n) = f(n-1) + f(n-2)` is also exponential. Isn't that simpler? :-) – Daniel Lubarov May 03 '11 at 07:52
  • Yes, I agree it is a somewhat convoluted approach. – hammar May 03 '11 at 10:32