Complexity of the method [duplicate]

StackOverflow https://stackoverflow.com/questions/18868804

  •  29-06-2022
  •  | 
  •  

Question

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);
}
Était-ce utile?

La solution

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:

fibonacci tree

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.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top