0
$\begingroup$

So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ignore the $d$ multipliers in the series for the Big-O time complexity of the algorithm

enter image description here

My initial thought is that the time complexity would be $db^d$ since the magnitude of d will affect the time complexity, but I clearly wasn't paying enough attention in first year when they went over Big-O notation. Any help would be greatly appreciated, thanks!

$\endgroup$

4 Answers 4

0
$\begingroup$

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 is also in $O(db^d)$, but a tighter bound is $O(b^d)$.

$\endgroup$
0
$\begingroup$

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 geometric series, easily to calculate. Now the sum is actually $y + y/b + y/b^2 + y/b^3 ...). Another simple geometric series, which gives you the exact result.

$\endgroup$
0
$\begingroup$

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 + d) b^d +1}{(b-1)^2}.$$

The target expression is $(d+1)s(d)-t(d)$.

$\endgroup$
0
$\begingroup$

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 have $b$ nodes. Can be written as $b^\color\red1$
  • At Level-$\color\red2$, there will be $b^\color\red2$ nodes.
  • At Level-$\color\red{d-1}$, there will be $b^{\color\red{d-1}}$ nodes.
  • At Level-$\color\red d$, we have $b^\color\red d$ nodes.

Now, sum of all nodes in previous level $$b^0+b^1+b^2+\ldots \ldots b^{d-1}$$It is a Geometric Progression with common ratio $b$ and first term $1$. Thus, using the summation formula, this sum will be

$$\frac{b^d-1}{b-1}$$

This sum is less than $b^d$. Thus, number of nodes in last term dominates. Hence, $$\mathcal O (b^d)$$


Mathematically : Assume we go till depth $d$ (0-indexed).

  • Then, we have to touch/process Level-0 nodes $d+1$ times.
    There is $1$ node at this level.
  • We are processing Level-1 nodes $d$ times.
    There will be $b$ nodes at Level-1 [Very definition of $b$, the branching factor]
  • Then, we will process Level-2 nodes $d-1$ times.
    There will be $b^2$ nodes.

.
.
.

  • At last, we will process Level-d nodes $1$ times.
    There will be $b^d$ nodes in Level-d.

Thus, we have $$(d+1)b^0 + (d)b^1 + (d-1)b^2 + \ldots \ldots + (1)b^d$$

Now, this is Arithmetico–geometric Progression (AGP).

If AGP is of the form $$\alpha\beta+(\alpha+\delta)\beta\gamma+(\alpha+2\delta)\beta\gamma^2+\ldots[\alpha+(n-1)\delta]\beta\gamma^{n-1}$$then it's sum is given by $$\frac{\alpha\beta-(\alpha+n\delta)\beta\gamma^n}{1-\gamma}+\frac{\delta\beta\gamma(1-\gamma^n)}{(1-\gamma)^2}$$

Comparing standard formula with our series, we can have

$\alpha$ as

$(d+1)$

$\beta$ as

$1$

$\delta$ as

$-1$

$\gamma$ as

$b$

$n$ as

$(d+1)$

Putting into the formula, and simplifying a bit, we will get $$\frac{(1-b)(d+1)+b(b^{d+1}-1)}{(1-b)^2}$$ which can be further simplified as $$\frac{2-2b-bd+b^{d+2}}{(1-b)^2}$$ [If any mistake in calculation, please comment]

Clearly $b^{d+2}$ is dominating.

Thus, it is $$\mathcal O (b^d)$$


$\endgroup$

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.