0
$\begingroup$

i have to calculate the asymptotic runtime of a nested sum:

Sum $\sum_{n=1}^{log_{4}(n)} \sum_{n=1}^{\sqrt{n}}1$

My solution is $\Theta(log(n) \cdot \sqrt{n})$, which is wrong, because the solution says $\Theta(\sqrt{n})$. I dont understand where my mistake is:

Sum $\sum_{i=1}^{log_{4}(n)} \sum_{j=1}^{\sqrt{n}}1 = \sum_{i=1}^{log_{4}(n)} \sqrt{n} = \sqrt{n} \sum_{i=1}^{log_{4}(n)}1 = \sqrt{n} \cdot (log(n)+1) =$ $ log(n) \cdot \sqrt{n} + \sqrt{n} \stackrel{?}{=} \Theta(log(n) \cdot \sqrt{n}) $

Maybe my formula is wrong. Here is the pseudo-code i have to analyse:

someFunc(n)
  i = n
  while (i >= 1)
   i=i/4;
   //we do sqrt(i) operations
   for j=1 to sqrt(i)
     do_some_atomic_op() //O(1)
   end
   //i will reduce in every step!
  end
end
$\endgroup$
  • 1
    $\begingroup$ Could you please clarify index notation in the sums? What does it mean from $n=1$ to $\sqrt{n}$? $\endgroup$ – fade2black Jul 30 '17 at 14:45
  • $\begingroup$ Sorry, this is wrong. I will change it. $\endgroup$ – M.Mac Jul 30 '17 at 14:45
  • $\begingroup$ Your notation doesn't make any sense whatsoever. The inner sum can be calculated in constant time, if the lower n is replaced with k, for example. I can only guess what the outer sum is supposed to be, so it's likely that the sum can be calculated in O (log n). $\endgroup$ – gnasher729 Jul 30 '17 at 16:58
  • $\begingroup$ "the asymptotic runtime of a nested sum" -- I have no idea what that means. Do you want to know how much time it costs to compute tha value of that some, or do you want aymptotics bounds on the value of the sum? $\endgroup$ – Raphael Jul 30 '17 at 17:07
  • 1
    $\begingroup$ Please check If I edited correctly. $\endgroup$ – fade2black Jul 30 '17 at 17:14
2
$\begingroup$

In fact you do change the value of $n$, see $n=n/4$, and so the while-loop results in $\sum_{i=1}^{\log_4{n}}{\sqrt{i}}$ which is equal to $\sqrt{1} + \sqrt{2} + \dots + \sqrt{\log_4{n}}$.

Upper bound $\sqrt{1} + \sqrt{2} + \dots +\sqrt{\log{n}} \leq \log{n}\sqrt{\log{n}}$ which is less than $\sqrt{n}$ for sufficiently large $n$s (you may prove it using induction or using some other techniques).

$\endgroup$
  • $\begingroup$ I see! Ah i see, the double sum is totally wrong! $\endgroup$ – M.Mac Jul 30 '17 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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