New answers tagged

0 votes

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 ...
user avatar
0 votes

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 ...
user avatar
  • 3,912
0 votes

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 ...
user avatar
  • 25.2k
0 votes
Accepted

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

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 ...
user avatar
  • 3,512
1 vote
Accepted

Rigorous distinction between search and optimization

A representation where the state space is all paths to the goal is completely unusable. It blows up the state space exponentially large. And it loses the structure that algorithms like A* make good ...
user avatar
  • 141k

Top 50 recent answers are included