Recurrence Tree for Recurrence Inequality

Question

I'm used to solving recurrences that are in the form of T(n) = ...

However, when analyzing an algorithm, its recurrence form is:

$$ T(n) < \sqrt{n} \cdot T(\sqrt{n}) + n $$

How do I solve a recurrence with an inequality?

Answer 1

Just like the equality case. In the present case, note that $T(n)/n\lt T(\sqrt{n})/\sqrt{n}+1$. Let $S(k)=T(2^{2^k})/2^{2^k}$, then $S(k)\lt S(k-1)+1$ hence $S(k)\lt S(0)+k$ for every $k$, and $T(2^{2^k})\lt2^{2^k}(T(2)/2+k)$, which you will probably want to transform into $$ T(n)\lt n\cdot(\log_2\log_2(n)+c). $$

Answer 2

If you write $H(n)=\sqrt n H(\sqrt n)+n$ and solve that, then (with appropriately chosen base cases) you can prove by induction that $T(n)<H(n)$. This is the best you can do, since the difference between the sides of your original inequality can be arbitrarily small.

Answer 3

Note that your recurrence relation will keep getting you one copy of $n$ every time you apply it recursively, until finally you get that taking $k$ square-roots of $n$ reduces you to the base case. Each time you take a square-root recursively, it reduces the log by a factor of two. So you are really dividing the log by 2 until you get to the base case. It will take $O(\log \log n)$ iterations to do this. This means that you will have $T(n) = O(n \log \log n)$.