4 Replies - 12945 Views - Last Post: 07 October 2012 - 08:06 PM

#1 byrandomby1  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 124
  • Joined: 08-March 11

Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 03:41 AM

Why is the time complexity of the Fibonacci recursive sequence O(2^n)?

int fib(int n)
    {
    if (n <= 2) return 1
    else return fib(n-1) + fib(n-2)
    }


How do I differentiate between O(2^n) and O(n^2)?

If there is a recursive function

int fib(int n)
    {
    if (n <= 3) return 1
    else return fib(n-1) + fib(n-2) + fib(n-3)
    }


would the time complexity be O(3^n)?

Is This A Good Question/Topic? 0
  • +

Replies To: Time complexity of Fibonacci sequence and other recursion

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10466
  • View blog
  • Posts: 38,793
  • Joined: 27-December 08

Re: Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 11:11 AM

The Fibonacci sequence is O(2^n). You can prove it mathematically. Remember the definition of Big-O: f(n) is O(g(n)) iff there exist constants C and k (positive integers) such that |f(x)| <= C*|g(x)| for all x >= k.

So we know that Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2^n. Now prove inductively that f(n) <= g(n) starting at some x. Then solve for C.

I have a Big-O proofs tutorial you may find helpful.
Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2101
  • View blog
  • Posts: 3,204
  • Joined: 21-June 11

Re: Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 11:46 AM

View Postmacosxnerd101, on 06 October 2012 - 08:11 PM, said:

The Fibonacci sequence is O(2^n).


Note that this does not automatically imply that the cost of calculating the Fibonacci sequence is also in O(2^n) (and more importantly Theta(2^n)) (and in fact there are many ways of calculating it that are O(n)). So you still need to show that this particular way of calculating the sequence takes a number of steps proportional to fib(n).
Was This Post Helpful? 1
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10466
  • View blog
  • Posts: 38,793
  • Joined: 27-December 08

Re: Time complexity of Fibonacci sequence and other recursion

Posted 06 October 2012 - 01:18 PM

That's a good point. Actually solving the recurrence relation mathematically would allow you to find the first n Fibonacci numbers in O(n) time. This particular solution is O(2^n).
Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: Time complexity of Fibonacci sequence and other recursion

Posted 07 October 2012 - 08:06 PM

Quote

Why is the time complexity of the Fibonacci recursive sequence O(2^n)?

The reason the recursive variation is O(2^n) is because it does a lot of redundant calculations. For example, you need to calculate fib(n-1) + fib(n-2). In order to find fib(n-1), you need to calculate fib(n-2)+fib(n-3). So, already all the work that goes into calculating fib(n-2) is done twice. To understand it conceptually, I suggest you pick a few numbers for n and draw out the corresponding recursive calls. You will see that fib(1) and fib(2) get called about O(2^n) times. To show it formally, you should try what Mac suggested.

Quote

How do I differentiate between O(2^n) and O(n^2)?

An easy way to conceptualize 2^n is thinking "if I increase n by one, then I just doubled the runtime." That means if you increase n by 2 then you doubled the already doubled runtime and so on. To conceptualize O(n^2), if you increase n by 1, then you roughly added 2*n units of time to the runtime.

Quote

would the time complexity be O(3^n)?

Yes.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1