0
$\begingroup$

I've tried to expand the recursion:

$$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$

We have a total of $\lfloor\log_2(n)\rfloor + 1$ elements in the recursion. So we can easily find an upper bound: $$T(n) = O(n\cdot \log_2(n))$$

The thing is, I'm not sure it's a tight upper bound. More over, I haven't been able to reach a tight lower bound from the recursion. I've tried to, but I didn't get to the same assymptotic bound I've found above.

Any help would be appreciated.

$\endgroup$
1
  • $\begingroup$ These T(n) = T(sqrt(n)) + ... questions are really coming into fashion, right? $\endgroup$
    – gnasher729
    Apr 17 at 23:21

5 Answers 5

0
$\begingroup$

You can use induction to show that $T(n) = O(n)$.

More concretely, try to prove using induction that you can find a $c\in \mathbb{R}^+$ and $n_0\in \mathbb{N}$ such that for all $n>n_0$, it will hold that $T(n) < cn$.

Basically, substituting this in the induction will reduce your recurrent formula into a simple equation that you will need to solve to find the suitable constants $c$ and $n_0$.


Hint: try picking $n_0>4$

$\endgroup$
1
  • $\begingroup$ Or try a really big n, like n = 2^1024 (over 300 decimal digits). $\endgroup$
    – gnasher729
    Mar 19 at 22:09
2
$\begingroup$

Taking the square root of $n$ halves the number of bits, so you indeed halve that number $\lg n$ times before the iterated square root falls below some predefined constant (say $4$).

Now we can write

$$n+\sqrt n+\sqrt[4]n+\sqrt[8]n+\cdots<n+\sqrt n+\sqrt n+\sqrt n+\cdots=n+\sqrt n\lg n,$$ which is $O(n)$.


Justification:

With $n=m^2$, $$\sqrt n\lg n\le n$$

becomes $$2m\lg m\le m^2$$ or $$2\lg m\le m,$$

which is true as of $m=4$.

$\endgroup$
2
  • $\begingroup$ Great answer. For the lower bound, is it safe to claim that $T(n) \ge 5n \ge n$, so $T(n) = \Omega(n)$, and in total we get $T(n) = \Theta(n)$? $\endgroup$
    – Yoxbox
    Mar 21 at 8:44
  • $\begingroup$ @Yoxbox: yes it is. $\endgroup$ Mar 21 at 10:54
0
$\begingroup$

Dropping the factor $5$ and reducing by $S(n):=\dfrac{T(n)}{5n}$, and with $S(10)=0$ (arbitrarily):

$$S(100)=\frac{S(10)}{10}+1=1$$ $$S(10000)=\frac{S(100)}{100}+1=1.01$$ $$S(100000000)=\frac{S(10000)}{10000}+1=1.000101$$ $$S(10000000000000000)=\frac{S(100000000)}{100000000}+1=1.00000001000101$$

It is clear that $S(n)$ gets closer and closer to $1$.

$$1<S(n)<(1+\epsilon)$$ where $\epsilon$ is a constant as small as you want, and $n>n_0$, giving

$$5n<T(n)<5(1+\epsilon)n.$$

$\endgroup$
0
$\begingroup$

We want to find, $T(n) = T(\sqrt{n}) + 5n$

Assume $T(\epsilon) = c > 1$, $\epsilon > 1$ .

So $T(n) = T(\epsilon^{2k}) \\ = c + 5(\epsilon^2 + \epsilon^4 + \cdots + \epsilon^{2k}) \\ < c + 5((k-1)\epsilon^{2(k-1)} + \epsilon^{2k})\\ = c + 5 (o(\epsilon^{2k}) + \epsilon^{2k}) = O(5n)$

$\endgroup$
4
  • $\begingroup$ @gnasher729 here you can try $2^{1024}$. Just play with the exponent, and leave $2$ for this moment. You will add some numbers with $1024$ bit and all other things to be added can be summed up to $600$ bit at most. $\endgroup$ Mar 21 at 18:03
  • $\begingroup$ If with $5n$ you mean "asymptotically no greater than $5n$", you are wrong. $\endgroup$ Mar 21 at 21:07
  • $\begingroup$ @Yves Why? Where is the problem? $\endgroup$ Mar 21 at 21:34
  • $\begingroup$ It is always greater than $5n$. $\endgroup$ Mar 22 at 8:44
0
$\begingroup$

Hint.

$$ T\left(2^{\log_2 n}\right) = T\left(2^{\frac 12\log_2 n}\right)+5n $$

or recasting

$$ R(z) = R\left(\frac z2\right)+5\cdot 2^z $$

and recasting again

$$ C(m) = C(m-1) + 5\cdot 2^{2^m} $$

and after solving, backwards...

$\endgroup$

Your Answer

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

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