3
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – k4kuz0 Mar 31 '16 at 12:57
  • $\begingroup$ 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})$. $\endgroup$ – Jay Mar 31 '16 at 13:11
  • $\begingroup$ Ah it suddenly clicked for me. Thanks. $\endgroup$ – k4kuz0 Mar 31 '16 at 13:15
  • 1
    $\begingroup$ Using Landau terms in nested fashion is prone to producing errors. It's better to be more explicit about the cost. $\endgroup$ – Raphael Mar 31 '16 at 15:37

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.