in Algorithms retagged by
419 views
0 votes
0 votes

void fun(int n)

{

   int j = 1, i = 0;

   while (i < n)

   {

       // Some O(1) task

       i = i + j;

       j++;

   }

}

Time complexity of the above code ?

in Algorithms retagged by
419 views

2 Comments

$O(n^{1/2})$
0
0
Explanation please..
0
0

1 Answer

1 vote
1 vote
Best answer

Initially i = 0  , j = 1

After 1st iteration , i = i + j  =  1    ,   j  = 1 + 1 = 2 [ as 'j' is incremented ]

After 2nd iteration , i = i + j  =  1 + 2 = 3  ,  j =  2 + 1 = 3

After 3rd iteration , i  = i + j  =   3 + 3  =  6  , j  =  4

So we can see

after xth iteration  , we get  i  =  sum of x consecutive terms starting from 1 

                                          =  x(x+1)/2

Also i keeps on incrementing till the condition :  i < n is true..

Hence , to find the  terminating condition we equate i to n..

So ,

              x(x+1)/2  =  n

   ==>     x2        =    n  [ As to find asymptotic bound , we need to consider dominating terms only and x2 is dominating here as it is the highest power term , Also constants are ignored..]

  ==>     x          =    sqrt(n)

Hence time complexity   =  O(sqrt(n))

selected by

2 Comments

Sir ,is it a formula

1+3 +6+10+... = X(x+1)/2
1
1
No it is say , i = 3  =  2(2+1)/2  =  3

                    i = 6  =  3(3+1)/2 =   6..

Likewise  at terminating condition i  =  x(x+1)/2
0
0