0
$\begingroup$

I tried to find the complexity of this recursion equation: $T(n)=\sqrt{n}T(\sqrt{n})+n$,

by doing couple of iterations and getting a general idea, but I completely got lost.

I'd really love your help with this.

The solution should be in Theta terms. What function of $n$, the input, does this recursion will "waste"..

And another question: Which function is asymptotically bigger:

$$f(n)=n\sum_{i=1}^{lgn}\frac{i}{2^{i}}\quad \text{ or }\quad g(n)=\sum_{i=1}^{n}\frac{1}{2^{i}}\quad ?$$

Thanks.

  • 0
    And I'm very sorry for overflowing with questions, it's just that I have a short-notice test to take tomorrow. I really appreciate the help.2011-07-09
  • 0
    Regarding the comparison of $f$ vs $g$, you must be kidding... Both series converge hence $f(n)=\Theta(n)$ and $g(n)=\Theta(1)$, end of story. Overflowing has its consequences...2011-07-09
  • 0
    Regarding $T$, rewriting the recursion as $T(n)/n=1+T(\sqrt{n})/\sqrt{n}$ yields immediately $T(n)=\Theta(n\log(n))$.2011-07-09
  • 3
    Nir, please post one question at a time. Neither categorization with tags, nor text search, nor going by the title work well if you put two questions into one.2011-07-09
  • 1
    @joriki: Ok, I will. @Didier: If you were less concentrate of insulting you would find out that you have a mistake :O, god forbid.2011-07-09
  • 0
    For which values of $n$ is the recursion defined? With $n = 1$ you get an obvious contradiction..2011-07-09
  • 0
    @Nir: *insulting*: Would you have an example? *mistake*: Would you have an example? *concentrate*: On this one, I plead guilty.2011-07-09
  • 1
    @Didier: Whatever. I'll write here an example tomorrow for your mistake regarding the recursion, i don't have time now. The answer is:$\Theta(nloglogn)$ and not what you wrote, so $you must be kidding$ to call yourself a professor.2011-07-09
  • 0
    @ZulfiqarIII: Initial values need to be specified in some range $[x,x^2)$, where $x>1$ to determine all values for $n>1$, and with $x<1$ to determine all values for $n<1$. As you say, the function isn't defined for $n=1$.2011-07-09
  • 2
    @Nir: Sure. Good luck for your test.2011-07-09
  • 0
    @Nir: Didier practically gave you the solution, even though the final answer is incorrect. I suggest you read his comment carefully. Good luck with your test.2011-07-09
  • 0
    @Didier: $\Theta(n \log n)$ is indeed incorrect and $\Theta(n \log \log n)$ is right, I believe.2011-07-09
  • 0
    @Aryabhata: Yes.2011-07-09
  • 0
    @Everybody: Let me suggest we go back to the worship of the cold but beautiful Goddess of mathematics we all love (and I include myself in the targets of this friendly admonestation).2011-07-09
  • 1
    @Listing: I find that slightly unfair. While I agree that Nir's response was combative and I would much prefer if this sort of exchange wouldn't take place, it's also true that "you must be kidding" isn't exactly a friendly response to the question, which was, though badly phrased and formatted, not insulting; so it's not quite fair to lay the entire blame for the ensuing escalation on Nir.2011-07-09
  • 4
    @joriki: believe it or not, I basically agree with your last comment. My "you must be kidding" was a way of expressing what I saw as a lack of thought from the OP before asking the second question of the post and if it may have been seen as insulting, then I withdraw it (I did not think it was, since the equivalent in my native language is rather friendly, but this is not an excuse).2011-07-09
  • 0
    @Lisitng: Didier himself knows he was wrong talking the way he did, by his answer above-"sure". I'm not one of his students to get insulted. If my question is funny he does not have to answer it and waste his time. I really appreciate his answers to my questions, one of them, gave him his highest score ever (52), so maybe not all my questions are dumb, BUT i don't appreciate disrespect.2011-07-09
  • 0
    I removed my comment, sorry for overreacting but I felt that what I read was very rude. Let us just stay on topic.2011-07-09
  • 2
    @Nir: Didier has accepted that you were offended by his wording; if you can also accept that that was an unintentional effect of an inauspicious translation from his native language, we can all be friends again ;-) I'm writing this because your comment that "he was wrong" also sounds like you're putting the blame solely on him, whereas I think if you accept that such misunderstandings sometimes occur then you might not react so strongly next time, which was also part of the problem in this case.2011-07-09
  • 0
    Nir: How did your test go? Hope it went well! :)2011-07-10
  • 0
    Theo: well it went O.k :) Thank you very much for asking! In calculus by the way, which you guys helped me a lot with, I got a very high score.. thanks again!2011-07-10

1 Answers 1

5

I take it that you meant to ask about the solution of the equation and its asymptotic behaviour, not its complexity. This is related to complexity in that if you can solve a problem of size $n$ by splitting it into roughly $\sqrt{n}$ parts of size roughly $\sqrt{n}$ and doing work $n$ in the process, $T$ gives the amount of work required for solving a problem of size $n$, and the asymptotic behaviour of that work determines the complexity; however, this is the complexity of the algorithm, not of the equation.

As Aryabhata pointed out in the comments, Didier's approach is good but the answer was wrong. Starting from Didier's rewritten version,

$$\frac{T(n)}n = \frac{T(\sqrt{n})}{\sqrt{n}}+1\;,$$

we can introduce $a(n)=T(n)/n$ to obtain

$$a(n)=a(\sqrt{n})+1\;.$$

With $b(k)=a(\mathrm e^k)$, this becomes

$$b(k)=a(\mathrm e^k)=a(\mathrm e^{k/2})+1=b(k/2)+1\;.$$

Then $c(j)=b(2^j)$ yields

$$c(j)=b(2^j)=b(2^j/2)+1=b(2^{j-1})+1=c(j-1)+1\;.$$

This is trivially solved by $c(j)=j+C(\{j\})$ (where $\{j\}$ is the fractional part of $j$), and retracing the substitutions yields

$$T(n)=na(n)=nb(\log n)=nc(\log_2\log n)=n(\log_2\log n+C(\{\log_2\log n\})\;.$$

This is $\Theta(n\log\log n)$ if $C$ is bounded (which in practice it would be).