Big-O of recursive functions (II)

Computer Science Level 1

int Fibonacci(unsigned int N){
    if (N==0 || N==1)
        return N;
    else
        return Fibonacci(N-1)+Fibonacci(N-2);
}

The function Fibonacci(N) , given above, runs in _ _ _ _ _ _ _ _ _ _ _ _ __ .

n^2

2^n

\log_n2

\log_2n

1 solution

Tasneem Khaled
Jan 19, 2018

If we draw a tree for a fibonacci (N) , we will see that for the first level , there is one sub-branch corresponding to 2^0=1, for the second level there are 2^1=2 sub branches, for the third level, there are 2^2= 4 branches and the sequence keeps going like this, leading to the conclusion of 2^n.

Big-O of recursive functions (II)

1 solution

0 pending reports