419 views

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 ?

$O(n^{1/2})$

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))

Sir ,is it a formula

1+3 +6+10+... = X(x+1)/2
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

1 vote
1
324 views