1
$\begingroup$

I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way:


$n = 2^k$

$2^{\frac{2}{k}}\cdot T\left(2^k\right)+\log2^k$

$2^{\frac{2}{k}}\cdot T\left(2^k\right)+k$

At that point i'm stuck and not sure how to handle the $2^{\frac{2}{k}}$ before the $T\left(2^k\right)$. I would also like which more tools are open to use at this problem.

$\endgroup$
2
  • 1
    $\begingroup$ For starters, how did you get that? You somehow had an error while substituting since when you substitute you need to get $2^{\frac{k}{2}}T(2^{\frac{k}{2}})+k$ $\endgroup$
    – nir shahar
    Jan 28, 2022 at 12:00
  • $\begingroup$ Your development is meaningless, as you list unrelated expressions. $\endgroup$
    – user16034
    Feb 28, 2022 at 16:13

2 Answers 2

1
$\begingroup$

For $n > 0$ we have

$$ \frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}}+c\frac{\ln n}{n} $$

calling $R(n) = \frac{T(n)}{n}$ we follow with

$$ R(n) = R(\sqrt{n})+c\frac{\ln n}{n} $$

but now

$$ R\left(2^{\log_2 n}\right) = R\left(2^{\log_2 \sqrt{n}}\right)+c\frac{\ln n}{n} $$

Calling now $\mathcal{R}(\cdot) = R\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we follow with

$$ \mathcal{R}(z) = \mathcal{R}\left(\frac z2\right)+c_1 z 2^{-z} $$

now using again a transformation with $\mathbb{R}(\cdot) = \mathcal{R}\left(2^{(\cdot)}\right)$ and $\mu = \log_2 z$ we follow with the recurrence

$$ \mathbb{R}(\mu) = \mathbb{R}(\mu-1) + c_1 2^{\mu}2^{-2^{\mu}} $$

with solution

$$ \mathbb{R}(\mu) = c_0 + 2c_1\sum_{k=0}^{u-1}2^{-2^{k+1}+k} $$

now going backwards with $\mu = \log_2 z$ and $z = \log_2 n$ we arrive at

$$ T(n) = n\left(c_0+2c_1\sum_{k=0}^{\log_2(\log_2 n)-1}2^{-2^{k+1}+k}\right) $$

and certainly

$$ T(n) \ge n c_0 + c_1\log_2 n $$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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