I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so: Fibonacci recurrence tree

Since the tree can have a maximum height of 'n' and at every step, there are 2 branches, the overall time complexity (brute force) to compute the nth fibonacci number is O(2^n).

Now, looking at the coin make change problem. If the coin denominations are [1, 5, 10, 25] and the input number to make change for is 'C', the recurrence tree should look something like this: enter image description here

In this case, the tree can have a maximum height of 'C' and the number of branches per step is 4 (The number of coin denominations we are given. Let's call this 'n'). With that being the case, shouldn't the time complexity be O(n^C). I read everywhere that the time complexity is O(C^n). Can someone please explain?

up vote 3 down vote accepted

First, when computing the $n$-th fibonacci number $F(n)$, the number of branches (leaves) is not $2^n$, but exactly $F(n)$. But you can say it is $O(2^n)$.

As for the coin change problem it is not $O(n^C)$. $n^C$ is a polynomial, while the number of branches in the tree grows exponentially. In other words, given $n$ number of coin denominations and constant $C$, each node has no more than $C$ children, and so the number of branches/leaves is at most $C\times C\times \dots C$ ($n$ times). In fact the actual number of branches is less than $C^n$, but is definitely bounded from above by $C^n$, and so is $O(C^n)$ (recall that big-O denotes the upper bound of a function).

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.