What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$
Where are you using that T(n) = c for n &lt;= 10? Your formula is wrong when the argument is less than 10. K = 1 is not the base case. N &lt;= 10 is the base case.
Clearly T(n) = c for n &lt;= 10, T(n) = c+3 if 10 &lt; n &lt;= 100, T(n) = c+6 if 100 &lt; n &lt;= 10,000, T(n) = c+9 if 10,000 &lt; n &lt;= 100,000,000 etc.
Let f(n) = log_10 (max (n, 10)) so for the four cases above we have f(n) = 1, 1 &lt; f(n) &lt;= 2, 2 &lt; f(n) &lt;= 4, 4 &lt; f(n) &lt;= 8 etc.
Let g(n) = ceil(log_2(f(n))), then g(n) = 0, 1, 2, 3 etc, and T(n) = c + 3 g(n).