0
$\begingroup$

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\,.$$

|cite|improve this question
$\endgroup$
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.