# Asymptotic runtime of a nested sum

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

• Could you please clarify index notation in the sums? What does it mean from $n=1$ to $\sqrt{n}$? – fade2black Jul 30 '17 at 14:45
• Sorry, this is wrong. I will change it. – M.Mac Jul 30 '17 at 14:45
• 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). – gnasher729 Jul 30 '17 at 16:58
• "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? – Raphael Jul 30 '17 at 17:07
• Please check If I edited correctly. – fade2black Jul 30 '17 at 17:14

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