Analyzing time complexity for change making algorithm (Brute force)

Question

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?

Answer 1

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).

• Morgan: The logic of branching_factor_max ^ max_height of recursive tree = max_number_of_recursive_calls (aka max number of nodes in tree) is correct so I must be missing something. Assuming the base algorithm is we make denomination.length recursive calls with N - denomination as target until target amount is 0 or below 0, then the max_branching_factor = denomination.length and the max_height assumes a poss denomination of 1 so is N. Why does this not lead to time complexity of denomination.length^N? Your logic makes sense, but I’m still struggling to find the error with mine or OPs.
• Neel Sandell: @Morgan I think this answer is wrong. It is known that for a perfect n-ary tree the number of nodes in the tree is $\frac{1- n^{layers}}{1-n}$ which evaluates to $n^{c}$.