Asymptotics of recurrence $f(x) = 8f(x/2) + O(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) &amp;= \frac{f(\sqrt{M}x)}{M} = \begin{cases} \frac{8}{M} f(\sqrt{M}x/2) + \Theta(1) &amp; \mbox{if }Mx^2 &gt; M \\
1 &amp; \mbox{if } Mx^2 \le M
\end{cases} \\
&amp;=
\begin{cases} 8g(x/2) + \Theta(1) &amp; \mbox{if }x &gt; 1 \\
1 &amp; \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)$.