0

Consider the following recurrence relation:

$$T(n) = 2T(\lceil{\sqrt{n}\rceil}) + 1 \text{ if } n >2$$

$$T(n) = n \text{ if } n \leq 2$$

I can see intuitively that

$$T(n) = O(\log{n})$$

because there are $O(\log\log{n})$ levels to the recursion and the value is doubled at each level.

Is there a nice formal proof of this result?

  • Consider $n$ of the form $2^{2^k}$ (power of two) first, solve the recurrence then. Setting $t(k) \stackrel{\rm def}{=} T(2^{2^k})$, this is $$t(k) = 2t(k-1)+1$$Then conclude under "reasonable assumptions on $T$" (as usual...): non-decreasing, relatively well-behaved, etc. – Clement C. Feb 26 '19 at 20:59

1 Answers1

1

$$ T(n) = 2T(\lceil{\sqrt{n}\rceil}) + 1 \text{ if } n >2 $$

is equivalent to

$$ T(\lceil n\rceil) = 2T(\lceil{\sqrt{n}\rceil}) + 1 \text{ if } n >2 $$

so calling

$T'(n) = T(\lceil n\rceil)$ we have

$$ T'(e^{\ln n}) = 2T'(e^{\frac 12\ln n})+1 $$

and calling $T''(z) = T'(e^z)$ we have

$$ T''(\ln n) = 2 T''(\frac 12\ln n) + 1 $$

or

$$ T''(2^{\log_2(\ln n)}) = 2T''(2^{\log_2(\ln n)-1})+1 $$

and now with $T'''(u) = T''(2^u)$ with $u = \log_2(\ln n)$

$$ T'''(u) = 2T'''(u-1)+1 $$

This is a linear recurrence equation with solution

$$ T'''(u) = C_1 2^{u-1}+2^u-1 $$

The return to $T(n)$ is left to the reader

Cesareo
  • 33,252