# Tag Info

### Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

Intuitively : Number of nodes in last level is more than sum of all nodes in Previous level. At Level-$\color\red0$, we have $1$ node. It can be written as $b^\color\red0$ At Level-$\color\red1$, we ...

### Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

Hint: $$s(d):=b^0+b^1+b^2+\cdots b^d=\frac{b^{d+1}-1}{b-1}$$ and by summation until $d+1$ and differentiation, t(d):=0b^0+1b^1+2b^2+\cdots db^d=\frac{\partial}{\partial b}s(d+1)=\frac{d b^{d+1} - (1 ...

### Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

Let x = $b^d$. The last term is x. The second to last is x * (2 / b). The third to last is $x * (3 / b^2)$, then $x * (4 / b^3)$ etc. Let y = $x * (1 + 1 / b + 1 / b^2 + 1 / b^3 ...)$. That's a simple ...
If $b, d$ goes to infinity, as all other sum factors are asymptotically less than $b^d$ (except the last one!), the mentioned time complexity function will be in $\Theta(b^d)$. Hence, this algorithm ...