9
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Morgan
    Commented Apr 20, 2019 at 4:02
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – Neel Sandell
    Commented Feb 22, 2022 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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