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 \frac{x}{\sqrt{M}}$$$$\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\frac{x}{\sqrt{M}}.$$$$\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}(8^k+M\times (\frac{x}{\sqrt{M}})^3)=\mathcal{O}(M\times (\frac{x}{\sqrt{M}})^3).$$$$\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).$$
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 \frac{x}{\sqrt{M}}$$, because in each step input $x$ divide by 2ドル$, until $$\frac{x}{2^k}\geq \sqrt{M} \rightarrow k\leq\log_2\frac{x}{\sqrt{M}}.$$
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}(8^k+M\times (\frac{x}{\sqrt{M}})^3)=\mathcal{O}(M\times (\frac{x}{\sqrt{M}})^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).$$
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 \frac{x}{\sqrt{M}}$$, because in each step input $x$ divide by 2ドル$, until $$\frac{x}{2^k}\geq \sqrt{M} \rightarrow k\leq\log_2\frac{x}{\sqrt{M}}.$$
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}(8^k+M\times (\frac{x}{\sqrt{M}})^3)=\mathcal{O}(M\times (\frac{x}{\sqrt{M}})^3).$$