# Explanation of a simple algorithm's Big O complexity

I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation:

Loop2(n)
for i := 0 to n
j := 0
s := 0
while s <= i
j := j + 1
s := s + j


I can see that the outer loop (alone) is run $O(n)$ times, and that the inner loop is $O(\sqrt n)$. However, the part that confuses me is that the correct answer, according to the paper, is $O(n \cdot \sqrt n)$.

I though that, since the inner loop is dependent on $i$, that it would be run $\sqrt i$ times, for $i$ going from $0..n$. Meaning that in total, the loop would run roughly $n$ times, making the whole algorithm $O(n\cdot n)=O(n^2)$. I kinda drew the logic from an analysis of insertion sort, where $$\sum_{i=0}^{n} n-i = O(n^2)$$

I think I remember the above correctly. Can anyone fix my broken logic here?

The inner loop is $O(\sqrt{i})$, you are correct. Since $i\leq n$, then $\sqrt{i}\leq \sqrt{n}$, and we have $n\times\sqrt{i}\leq n\times\sqrt{n}$. Hence the complexity is $O(n\sqrt{n})$.
• I'm not sure I follow. The inner loop is $O(\sqrt i)$, but since the loop is executed $n$ times, then the inner loop is essentially $\sum_{i=0}^{n} \sqrt i$. Is this just $O(\sqrt n)$? Why? – k4kuz0 Mar 31 '16 at 12:57
• It's a while inside a for. For each $i$, the while takes $O(\sqrt{i})$. There are $n$ for-iterations, so $O(n\sqrt{n})$. – Jay Mar 31 '16 at 13:11