CODEWITHSUNDEEP
mathbig-otime-complexityasymptotic-complexity
conquester
conquester

Reputation: 1132

Determining the Big-O growth rate of this function

I cannot determine how to determine the growth rate of these type of functions. 

void A(int n){
 int i=1, s=1;
 while(s<=n){
   i++;
   s=s+i;
   cout<<"hi";
   }
}

It is given that this is O(sqrt(n)) but I cannot figure how?

Upvotes: 1

Views: 65

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

If you look at the values of s across each iteration, you'll see that it goes 1, 3, 6, 10, 15, etc. These numbers are called the triangular numbers and are numbers of the form k(k+1)/2 (it's common to prove this as an exercise in induction.)

The loop stops running as soon as s exceeds n. On iteration k, the value of s is k(k+1)/2, so you can count up the number of iterations by solving for k in k(k+1)/2. Try doing that and seeing what you find. Does that explain the square root?

Upvotes: 2

Related Questions