Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$

Question

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

• nir shahar: Time hierarchy theorem maybe?
• Yuval Filmus: The condition $x^2 > M$ is the same as the condition $x > \sqrt{M}$ (assuming $x$ is non-negative).
• Yuval Filmus: You can use the master theorem.

Answer 1

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

• Avv: Thank you. Very clear answer. Why you please multiplied by $M$ in $if~Mx^2 \gt M$?
• Steven: By definition of $f,ドル we can replace $f(y)$ with 8ドルf(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$.

Answer 2

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