How to solve this recurrence using recursion tree method
Break it up into parts you can handle.

$\max\,\{\sqrt{n},2\} = \sqrt{n}$ if, and only if, $n&gt;3$, so rewrite the recurrence as

$$\begin{align*}
T(n) &amp;= T(\lceil\sqrt{n}\,\rceil) + n &amp;&amp; \text{for } n&gt;3\\
T(n) &amp;= T(\lceil n/2\rceil) + n &amp;&amp;\text{for } n\leq 3\,.
\end{align*}$$

At that point, I think it's reasonable to solve the $n\leq 3$ part by direct substitution and then use required method for the $n&gt;3$ case.

By the way, you also need a case for $T(1)$, since the general equation gives $T(1) = T(\lceil\tfrac12\rceil)+1 = T(1)+1$, which is impossible.