# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.9487412,"math_prob":0.9999014,"size":812,"snap":"2019-51-2020-05","text_gpt3_token_len":246,"char_repetition_ratio":0.11509901,"word_repetition_ratio":0.0,"special_character_ratio":0.32142857,"punctuation_ratio":0.13402061,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000091,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-25T12:43:19Z\",\"WARC-Record-ID\":\"<urn:uuid:65f5743d-5ac3-4536-b04b-a1c4a729b45e>\",\"Content-Length\":\"139143\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:cb8faf6a-3ffd-4944-b005-7430834424c0>\",\"WARC-Concurrent-To\":\"<urn:uuid:252ceec8-fa7c-43cb-a7e5-9001085335cc>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/55245/explanation-of-a-simple-algorithms-big-o-complexity\",\"WARC-Payload-Digest\":\"sha1:EMDMJN5WFY2AKAFPGZWFK7HDSPSZ5KAR\",\"WARC-Block-Digest\":\"sha1:5WN5DI7JZ3EALJKLTRDJ57GC5JWOEEY3\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579251672440.80_warc_CC-MAIN-20200125101544-20200125130544-00344.warc.gz\"}"}