Explanation of a simple algorithm's Big O complexity

Question

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?

• Raphael: You need more structure in your analysis; see here. There are also some examples available: algorithm-analysis+loops

Answer 1

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

• k4kuz0: 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?
• Jay: 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})$.
• k4kuz0: Ah it suddenly clicked for me. Thanks.
• Raphael: Using Landau terms in nested fashion is prone to producing errors. It's better to be more explicit about the cost.