How to solve this using the recursive tree method? I'm stuck with the $\max$.
$$T(n) = T\left(\left\lceil \frac{n}{\max\,\{\sqrt{n},2\}}\right\rceil\right) + n\,.$$
0
$\begingroup$
$\endgroup$
5
$\begingroup$
$\endgroup$
Break it up into parts you can handle.
$\max\,\{\sqrt{n},2\} = \sqrt{n}$ if, and only if, $n>3$, so rewrite the recurrence as
$$\begin{align*} T(n) &= T(\lceil\sqrt{n}\,\rceil) + n && \text{for } n>3\\ T(n) &= T(\lceil n/2\rceil) + n &&\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>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.
answered Mar 7 '15 at 12:00
-
$\begingroup$ Thanks, for the quick response. But I already started to solve it from the same method you have pointed with n<4 and n>=4 . But I got stuck with a infinity sum of a series 1/n^(1/(2^(i))) $\endgroup$ – Malith Mar 7 '15 at 12:47
-
$\begingroup$ If you really need to take that sum to infinity, something has gone wrong. The infinite sum doesn't converge, since $1/\sqrt[2^i]{n} \to 1$ as $i\to\infty$. $\endgroup$ – David Richerby Mar 7 '15 at 13:30
