Complexity of the method [duplicate]

Question

This question already has answers here:

Computational complexity of Fibonacci Sequence (12 answers)

Closed 8 years ago.

I was asked this in an interview.WHat is the complexity of this method??

static int magic(int n) {
    System.out.println( count+" "+ n);
    count++;
    return (n < 2) ? n : magic(n - 1) + magic(n - 2);
}

Answer 1

The complexity is exponential.

The base case aside (when n is < 2), each call to the method will call itself two times. You can draw a binary tree representing the call. For example if you call magic with 5 as a parameter:

The tree is not perfectly balanced but it doesn't change the big O notation, which is O(2^n).

Your algorithm is a fibonnaci sequence algorithm, so you can read plenty about it on the internet, including how to change its complexity to polynomial time.