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

  • $\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$ – Yuval Filmus May 5 at 12:17
  • 1
    $\begingroup$ You can use the master theorem. $\endgroup$ – Yuval Filmus May 5 at 12:17

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


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


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.