Printable View
I am having a really hard time trying to grasp this concept. I understand the basics and can get the big O notation of simple algorithms but I need help with stuff a little more complex....specifically this one..
public static int fibEfficient(int n){
cntE++;
if(n<=2) return 1;
if(n==3)return 2;
else
return 2*(fibEfficient(n - 2)) + fibEfficient(n - 3);
}
can anyone tell me what it is, how to find it..PLEASE!!??
Finding the runtime of recursive algorithms can be done by 3 methods:
1. Using the Master Theorem, if it fits.
2. Developing the recursion formula that represents the runtime of the algorithm.
3. Using simple reasoning if possible.
If your'e using method 2 or 3, you will have to prove by induction that the runtime boundary you found holds for any n.
In your case, the Master Theorem does not hold, developing a recursion formula might be a bit complex but using simple reasoning you can see that if each recursive call is done in O(1) (some if statements, one increment and another recursive call - altogether it's O(1)), and there are at most 2 recursive calls done from each recursive call, you can draw a binary tree of recursive calls that looks like this:
The node numbers represent the value of the passed parameter in each recursive call. The height of this tree is at most n. This is because the leftmost branch is the longest and it's length is at most n (values decrease by one on each consecutive level).Code:n
n-1 n-2
n-2 n-3 n-3 n-4
. .
. .
Hence, the number of nodes in the tree are at most 2^n.
For each tree node, the algorithm executes O(1) operations and therefore the algorithm runtime has to be O(2^n).
All of this reasoning is just meant to get a speculative runtime boundary. To complete the proof, you still need to show(using induction) that this boundary holds for any n.
Regards,
Zachm
http://www.google.com/search?hl=en&q...&aq=f&oq=&aqi=Quote:
Originally Posted by paret