consider the given code snippet and find its time complexity.

Question

Although it is a computer science topic,still i am posting this because this question wants us to solve a good sequence and series.

Question

consider the given code snippet and find its time complexity.

   Void fun(int n){

     int i=1;
     int s=i;

     while(s<n){
                ++i;
                s=s+i;
               }

      }

My Approach

analysing the code snippet ,number of times while loop being executed gives the time complexity.while loop is executed by following the given sequence.

$$(1+2)+(1+2+3)+(1+2+3+4)...(1+2+3+4+....n)$$

$$=1 \times n +2 \times (n-1) + 3 \times (n-2) +....n \times 1 $$

but i am clueless to move forward.please help me out.

Answer 1

As @ShervinSorouri allready pointed out, your sequence is wrong.

After the $j$-th iteration you will have $$ s = 1+2+3+ \cdots + (j+1) $$ which is the arithmetic series with the result $$ s = \frac{(j+2)(j+1)}{2} \approx \tfrac{1}{2}j^2 $$ for large j. To surpass $n$ you'll need $$ j \approx 2\sqrt{n} $$ I guess this is the complexity you are looking for.