retagged by
603 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 ?

retagged by

1 Answer

Best answer
1 votes
1 votes

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

Related questions

1 votes
1 votes
0 answers
1
srestha asked May 19, 2019
594 views
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
0 votes
0 votes
1 answer
2
eyeamgj asked Jun 24, 2018
397 views
consider the following c program A(n){if(n<=1)return(n2 +n+1)elsereturn(5A(n/2)+3A(n/2)+MA(n))}where MA(n) has complexity O(n2).1.what is the recurrence relation for valu...
1 votes
1 votes
1 answer
3
nikkey123 asked Jan 3, 2018
379 views
0 votes
0 votes
1 answer
4
Surya Dhanraj asked Oct 24, 2017
467 views
An array a of unknown size is filled with special symbol let's say # . Time required to find the size of a is:Please give proper explanation