2
$\begingroup$

What is the asymptotic rate of growth of the following recurrence relation?

$$ f(x) = \begin{cases} 8f(x/2) + Θ(1) & \text{ if } x^2 > M, \\ M & \text{ if } x^2 \leq M. \end{cases} $$ Here $M$ is a constant.

I'm not sure how to do it with the condition on $x^2$.

$\endgroup$
3
  • $\begingroup$ Time hierarchy theorem maybe? $\endgroup$
    – nir shahar
    May 5 at 12:14
  • 2
    $\begingroup$ The condition $x^2 > M$ is the same as the condition $x > \sqrt{M}$ (assuming $x$ is non-negative). $\endgroup$ May 5 at 12:17
  • 1
    $\begingroup$ You can use the master theorem. $\endgroup$ May 5 at 12:17
3
$\begingroup$

The case $x^2 \le M$ has no effect on the asymptotic growth rate of $f$ since it is essentially telling you that $f(x) = \Theta(1)$ whenever $x$ is (at most) a constant.

Then you can use standard methods (e.g., the Master theorem) to show that $f(x) = \Theta(x^3)$.

Perhaps the following transformation will make this more evident. Define $g(x) = \frac{f(\sqrt{M}x)}{M}$, then: $$ \begin{align*} g(x) &= \frac{f(\sqrt{M}x)}{M} = \begin{cases} \frac{8}{M} f(\sqrt{M}x/2) + \Theta(1) & \mbox{if }Mx^2 > M \\ 1 & \mbox{if } Mx^2 \le M \end{cases} \\ &= \begin{cases} 8g(x/2) + \Theta(1) & \mbox{if }x > 1 \\ 1 & \mbox{if } x \le 1 \end{cases}. \end{align*} $$

Since $g(x) = \Theta(x^3)$, you have $f(x) = Mg(\frac{x}{\sqrt{M}}) = \Theta(M \frac{x^3}{M^{3/2}} ) = \Theta(x^3)$.

$\endgroup$
2
  • $\begingroup$ Thank you. Very clear answer. Why you please multiplied by $M$ in $if~Mx^2 \gt M$? $\endgroup$
    – Avra
    14 hours ago
  • 1
    $\begingroup$ By definition of $f$, we can replace $f(y)$ with $8f(y/2) + \Theta(1)$ only when $y^2 > M$. In our case $y$ is $\sqrt{M}x$ and hence the condition is $(\sqrt{M}x)^2 > M$ or, equivalently, $Mx^2 > M$. $\endgroup$
    – Steven
    13 hours ago
1
$\begingroup$

First, simplify $f(x)$ conditions: $$f(x) = \begin{cases} 8f(x/2) + Θ(1) & \text{ if } x > \sqrt{M}, \\ M & \text{ if } x\leq \sqrt{M}. \end{cases}$$ Now, if you draw recursion tree $\mathbb{T}$ of $f(x)$, each internal node has $8$ children, on other hand, the height of $\mathbb{T}$
$$\log_2 x-\log_2 \sqrt{M}=\log_2 \left(\frac{x}{\sqrt{M}}\right)$$, because in each step input $x$ divide by $2$, until $$\frac{x}{2^k}\geq \sqrt{M} \rightarrow k\leq\log_2\left(\frac{x}{\sqrt{M}}\right).$$

From full trees we know that, Since the number of leaves in a full tree is $\#\text{(number of leaves)}^k$ then we get the following series ( note that leaves of $\mathbb{T}$ has value $M$) $$\sum_{i=0}^{k-1}8^i+M 8^k=\mathcal{O}\left(8^k+M\times \left(\frac{x}{\sqrt{M}}\right)^3\right)=\mathcal{O}\left(M\times \left(\frac{x}{\sqrt{M}}\right)^3\right).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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