Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why doesn't this Fibonacci Number function work in O(log N)?

Tags:

fibonacci

So the Fibonacci number for log (N) — without matrices.

Ni // i-th Fibonacci number
= Ni-1 + Ni-2              // by definition
= (Ni-2 + Ni-3) + Ni-2     // unwrap Ni-1
= 2*Ni-2 + Ni-3            // reduce the equation
= 2*(Ni-3 + Ni-4) + Ni-3   //unwrap Ni-2
                           // And so on
= 3*Ni-3 + 2*Ni-4
= 5*Ni-4 + 3*Ni-5
= 8*Ni-5 + 5*Ni-6

= Nk*Ni-k + Nk-1*Ni-k-1

Now we write a recursive function, where at each step we take k~=I/2.

static long N(long i)
{
    if (i < 2) return 1;
    long k=i/2;
    return N(k) * N(i - k) + N(k - 1) * N(i - k - 1);
}

Where is the fault?

like image 287
Yellowfun Avatar asked Mar 07 '18 21:03

Yellowfun


People also ask

What is Big O for Fibonacci?

Thus, the complexity of fibonacci is O(Fn) = O(ϕn). This is approximately O(1.618n).

What is the time complexity of nth Fibonacci number?

Time Complexity: Hence the time taken by recursive Fibonacci is O(2^n) or exponential.

What is the recursive formula for the Fibonacci sequence Tennessee?

Mathematically Fibonacci numbers can be written by the following recursive formula. What this means is, the time taken to calculate fib(n) is equal to the sum of time taken to calculate fib(n-1) and fib(n-2). This also includes the constant time to perform the previous addition. but this is not the tight upper bound.


2 Answers

You get a recursion formula for the effort: T(n) = 4T(n/2) + O(1). (disregarding the fact that the numbers get bigger, so the O(1) does not even hold). It's clear from this that T(n) is not in O(log(n)). Instead one gets by the master theorem T(n) is in O(n^2).

Btw, this is even slower than the trivial algorithm to calculate all Fibonacci numbers up to n.

like image 79
Henry Avatar answered Oct 13 '22 07:10

Henry


The four N calls inside the function each have an argument of around i/2. So the length of the stack of N calls in total is roughly equal to log2N, but because each call generates four more, the bottom 'layer' of calls has 4^log2N = O(n2) Thus, the fault is that N calls itself four times. With only two calls, as in the conventional iterative method, it would be O(n). I don't know of any way to do this with only one call, which could be O(log n).

An O(n) version based on this formula would be:

static long N(long i) {
    if (i<2) {
        return 1;
    }
    long k = i/2;
    long val1;
    long val2;
    val1 = N(k-1);
    val2 = N(k);
    if (i%2==0) {
        return val2*val2+val1*val1;
    }
    return val2*(val2+val1)+val1*val2;
}

which makes 2 N calls per function, making it O(n).

like image 32
Temsia Carrolla Avatar answered Oct 13 '22 08:10

Temsia Carrolla