I've written a recursive and I'm trying to find the Big-O for it, but I'm having some difficulty deciding the exact big-o, any help is appreciated.
The code is as follows:
So far I've figured out that it's between 2^n and n^2. But one seems like an overestimate and the other seems like an underestimate.
Once again, appreciate any hints.
--GiLtY
PS. I started to doing the BigO in components: O(h-1) + O(h-2) + 1. I then tried to expand the components, and eventually I figure out that on each expansion, the total number of terms is 2^n, where n is the nth expasion since the original equation. But the problem arises because O(0) = 1, and for some expansions i'd have O(c), where c is a negative number (if that's the case I should just discard it). I'm having problem factoring this phenonmanon into the calculation of the Big-O
The code is as follows:
So far I've figured out that it's between 2^n and n^2. But one seems like an overestimate and the other seems like an underestimate.
Once again, appreciate any hints.
--GiLtY
PS. I started to doing the BigO in components: O(h-1) + O(h-2) + 1. I then tried to expand the components, and eventually I figure out that on each expansion, the total number of terms is 2^n, where n is the nth expasion since the original equation. But the problem arises because O(0) = 1, and for some expansions i'd have O(c), where c is a negative number (if that's the case I should just discard it). I'm having problem factoring this phenonmanon into the calculation of the Big-O
Facebook
Twitter