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

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

• Time hierarchy theorem maybe? May 5 at 12:14
• The condition $x^2 > M$ is the same as the condition $x > \sqrt{M}$ (assuming $x$ is non-negative). May 5 at 12:17
• You can use the master theorem. 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)$$.

• Thank you. Very clear answer. Why you please multiplied by $M$ in $if~Mx^2 \gt M$?
– Avra
16 hours ago
• 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$. 14 hours ago

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