Skip to main content
added 113 characters in body
Source Link
user16034
user16034

Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,

$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$ is of the form

$$S(m)=S(m-1)+c'2^{m-2^m}.$$

Then by induction,

$$S(m)=S_0+c'\sum_{k=1}^m2^{k-2^k},$$

which is

$$\frac{T(n)}{n}=S_0+c'\sum_{k=1}^{\lg\lg n}2^{k-2^k}.$$

The terms of the sum are

$$2^{-1},2^{-2},2^{-5},2^{-14},2^{-20},\cdots$$ so the sum converges very quickly and is bounded above by $0.7815$.

Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,

$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$ is of the form

$$S(m)=S(m-1)+c'2^{m-2^m}.$$

Then by induction,

$$S(m)=S_0+c'\sum_{k=1}^m2^{k-2^k},$$

which is

$$\frac{T(n)}{n}=S_0+c'\sum_{k=1}^{\lg\lg n}2^{k-2^k}.$$

Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,

$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$ is of the form

$$S(m)=S(m-1)+c'2^{m-2^m}.$$

Then by induction,

$$S(m)=S_0+c'\sum_{k=1}^m2^{k-2^k},$$

which is

$$\frac{T(n)}{n}=S_0+c'\sum_{k=1}^{\lg\lg n}2^{k-2^k}.$$

The terms of the sum are

$$2^{-1},2^{-2},2^{-5},2^{-14},2^{-20},\cdots$$ so the sum converges very quickly and is bounded above by $0.7815$.

Source Link
user16034
user16034

Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,

$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$ is of the form

$$S(m)=S(m-1)+c'2^{m-2^m}.$$

Then by induction,

$$S(m)=S_0+c'\sum_{k=1}^m2^{k-2^k},$$

which is

$$\frac{T(n)}{n}=S_0+c'\sum_{k=1}^{\lg\lg n}2^{k-2^k}.$$