14

I took discrete math (in which I learned about master theorem, Big Theta/Omega/O) a while ago and I seem to have forgotten the difference between O(logn) and O(2^n) (not in the theoretical sense of Big Oh). I generally understand that algorithms like merge and quick sort are O(nlogn) because they repeatedly divide the initial input array into sub arrays until each sub array is of size 1 before recursing back up the tree, giving a recursion tree that is of height logn + 1. But if you calculate the height of a recursive tree using n/b^x = 1 (when the size of the subproblem has become 1 as was stated in an answer here) it seems that you always get that the height of the tree is log(n).

If you solve the Fibonacci sequence using recursion, I would think that you would also get a tree of size logn, but for some reason, the Big O of the algorithm is O(2^n). I was thinking that maybe the difference is because you have to remember all of the fib numbers for each subproblem to get the actual fib number meaning that the value at each node has to be recalled, but it seems that in merge sort, the value of each node has to be used (or at least sorted) as well. This is unlike binary search, however, where you only visit certain nodes based on comparisons made at each level of the tree so I think this is where the confusion is coming from.

So specifically, what causes the Fibonacci sequence to have a different time complexity than algorithms like merge/quick sort?

loremIpsum1771
  • 2,497
  • 5
  • 40
  • 87

7 Answers7

26

The other answers are correct, but don't make it clear - where does the large difference between the Fibonacci algorithm and divide-and-conquer algorithms come from? Indeed, the shape of the recursion tree for both classes of functions is the same - it's a binary tree.

The trick to understand is actually very simple: consider the size of the recursion tree as a function of the input size n.

In the Fibonacci recursion, the input size n is the height of the tree; for sorting, the input size n is the width of the tree. In the former case, the size of the tree (i.e. the complexity) is an exponent of the input size, in the latter: it is input size multiplied by the height of the tree, which is usually just a logarithm of the input size.

More formally, start by these facts about binary trees:

  • The number of leaves n is a binary tree is equal to the the number of non-leaf nodes plus one. The size of a binary tree is therefore 2n-1.
  • In a perfect binary tree, all non-leaf nodes have two children.
  • The height h for a perfect binary tree with n leaves is equal to log(n), for a random binary tree: h = O(log(n)), and for a degenerate binary tree h = n-1.

Intuitively:

  • For sorting an array of n elements with a recursive algorithm, the recursion tree has n leaves. It follows that the width of the tree is n, the height of the tree is O(log(n)) on the average and O(n) in the worst case.

  • For calculating a Fibonacci sequence element k with the recursive algorithm, the recursion tree has k levels (to see why, consider that fib(k) calls fib(k-1), which calls fib(k-2), and so on). It follows that height of the tree is k. To estimate a lower-bound on the width and number of nodes in the recursion tree, consider that since fib(k) also calls fib(k-2), therefore there is a perfect binary tree of height k/2 as part of the recursion tree. If extracted, that perfect subtree would have 2k/2 leaf nodes. So the width of the recursion tree is at least O(2^{k/2}) or, equivalently, 2^O(k).

The crucial difference is that:

  • for divide-and-conquer algorithms, the input size is the width of the binary tree.
  • for the Fibonnaci algorithm, the input size is it the height of the tree.

Therefore the number of nodes in the tree is O(n) in the first case, but 2^O(n) in the second. The Fibonacci tree is much larger compared to the input size.

You mention Master theorem; however, the theorem cannot be applied to analyze the complexity of Fibonacci because it only applies to algorithms where the input is actually divided at each level of recursion. Fibonacci does not divide the input; in fact, the functions at level i produce almost twice as much input for the next level i+1.

kfx
  • 8,136
  • 3
  • 28
  • 52
  • 1
    So because the fib sequence simply decrements for each recursive call, it height of the tree would be linear as opposed to logarithmic like for merge sort which repeatedly halves the input size. And the width of the tree is specifically **2**^k because there are two recursive calls in the return statement and because there are repeated subproblems being solved? – loremIpsum1771 Jan 09 '16 at 21:48
  • Yes, there are `k` levels (because for each `i`, `fib(i)` evaluates `fib(i-1)`), and O(2^k) leaves, because `i+1` level of the tree has approximately twice as many nodes as the `i`-th level. – kfx Jan 09 '16 at 21:53
  • Is drawing out the recursive tree the only way to know that the i+1 has twice as many nodes as the previous level? I'm just trying to get the intuition for the width? – loremIpsum1771 Jan 09 '16 at 22:10
  • No, but the drawing makes things much easier. The important thing to notice is that each call of `fib` spawns two more calls of `fib` for all except very small values (`<=2`). Therefore the next level has twice as much `fib` calls. Same thing of course happens with mergesort, quicksort, etc. The shape of the recursion tree is basically the same (a binary tree) for many different functions. – kfx Jan 09 '16 at 22:16
  • Oh ok, I'm starting to get it now. So essentially, since each call makes 2 other calls at each tree level ```k```, it is O(2^k) and it would be O(3^k) or O(4^k) if there were 3 or four calls, respectively,made at each node. And even though algorithms like merge sort have the same recursion trees as fib, it seems the difference is in the operation being done. Since fib requires the summing of all of the nodes on each level (which is 2^n), it is O(2^n). If divide and conquer algos required this summing as well, they would also be exponential right? – loremIpsum1771 Jan 09 '16 at 23:06
  • I don't see why you think the operation would make a large difference. Actually, merging a list of sorted number is a far more complex more operation than adding two numbers, isn't it? Focus on the size of the tree - it's the necessary and sufficient difference. I'll expand the answer with a more rigorous math. – kfx Jan 10 '16 at 09:23
  • Makes sense, that's what I was getting at. Divide and Conquer Algorithms divide the input at each step while algorithms like Fibonacci don't, creating more input at each successive step, thus, growing the size (width) of the tree with each recursive call. – loremIpsum1771 Jan 11 '16 at 02:05
7

To address the core of the question, that is "why Fibonacci and not Mergesort", you should focus on this crucial difference:

  • The tree you get from Mergesort has N elements for each level, and there are log(n) levels.
  • The tree you get from Fibonacci has N levels because of the presence of F(n-1) in the formula for F(N), and the number of elements for each level can vary greatly: it can be very low (near the root, or near the lowest leaves) or very high. This, of course, is because of repeated computation of the same values.

To see what I mean by "repeated computation", look at the tree for the computation of F(6):

fib(6) computation tree
Fibonacci tree picture from: http://composingprograms.com/pages/28-efficiency.html

How many times do you see F(3) being computed?

William
  • 2,695
  • 1
  • 21
  • 33
  • It seems that some of the other answers are suggesting that the difference is in the fact that algorithms like merge sort get to their base condition by reducing the input size by a factor for each recursive call while algorithms like Fibonacci and Towers of Hanoi only reduce the size by addition/subtraction each time, getting to the base case a lot slower. But you're saying that the repeated computations (which can be solved by DP/Memoization) is what causes the difference? Or is it both? – loremIpsum1771 Jan 09 '16 at 21:25
  • The problem lies on the fact that the same problem is repeated. This is a recursive implementation of the sum of the first N numbers: `S(N) = N + S(N-1)`, the base case being `S(0) = 0`. The reduction is by addition/subtraction, however this is O(N). – William Jan 09 '16 at 21:27
  • Notice that, of course, if you add memoization then Fibonacci becomes O(n). – William Jan 09 '16 at 21:36
3

Consider the following implementation

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

Let's denote T(n) the number of operations that fib performs to calculate fib(n). Because fib(n) is calling fib(n-1) and fib(n-2), it means that T(n) is at least T(n-1) + T(n-2). This in turn means that T(n) > fib(n). There is a direct formula of fib(n) which is some constant to the power of n. Therefore T(n) is at least exponential. QED.

Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
3

To my understanding, the mistake in your reasoning is that using a recursive implementation to evaluate f(n) where f denotes the Fibonacci sequence, the input size is reduced by a factor of 2 (or some other factor), which is not the case. Each call (except for the 'base cases' 0 and 1) uses exactly 2 recursive calls, as there is no possibility to re-use previously calculated values. In the light of the presentation of the master theorem on Wikipedia, the recurrence

f(n) = f (n-1) + f(n-2)

is a case for which the master theorem cannot be applied.

Codor
  • 17,447
  • 9
  • 29
  • 56
3

With the recursive algo, you have approximately 2^N operations (additions) for fibonacci (N). Then it is O(2^N).

With a cache (memoization), you have approximately N operations, then it is O(N).

Algorithms with complexity O(N log N) are often a conjunction of iterate over every item (O(N)) , split recurse, and merge ... Split by 2 => you do log N recursions.

guillaume girod-vitouchkina
  • 3,061
  • 1
  • 10
  • 26
3

Merge sort time complexity is O(n log(n)). Quick sort best case is O(n log(n)), worst case O(n^2).

The other answers explain why naive recursive Fibonacci is O(2^n).

In case you read that Fibonacci(n) can be O(log(n)), this is possible if calculated using iteration and repeated squaring either using matrix method or lucas sequence method. Example code for lucas sequence method (note that n is divided by 2 on each loop):

/* lucas sequence method */
int fib(int n) {
    int a, b, p, q, qq, aq;
    a = q = 1;
    b = p = 0;
    while(1) {
        if(n & 1) {
            aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
        }
        n /= 2;
        if(n == 0)
            break;
        qq = q*q;
        q = 2*p*q + qq;
        p = p*p + qq;
    }
    return b;
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61
1

As opposed to answers master theorem can be applied. But master theorem for decreasing functions needs to be applied instead of master theorem for dividing functions. Without theorem with following recurrence relation with substitution it can be solved,

f(n) = f(n-1) + f(n-2)

f(n) = 2*f(n-1) + c

let assume c is equal 1 since it is constant and doesn't affect the complexity

f(n) = 2*f(n-1) + 1

and substitute this function k times

f(n) = 2*[2*f(n-2) +1 ] + 1   
f(n) = 2^2*f(n-2) + 2 + 1


f(n) = 2^2*[2*f(n-3) + 1] +2 + 1 
f(n) = 2^3*f(n-3) + 4 + 2 + 1
.
.
.
f(n) = 2^k*f(n-k) + 2^k-1 + 2^k-2 + ... + 4 + 2 + 1

now let's assume n=k

f(n) = 2^n*f(0) + 2^n-1 + 2^n-2 + ... + 4 + 2 + 1

f(n) = 2^n+1 thus complexity is O(2^n)

Check this video for master theorem for decreasing functions.

Tamer
  • 91
  • 2
  • 10