CODEWITHSUNDEEP
algorithm
DinhNguyen
DinhNguyen

Reputation: 356

What is the big O notation and how do I calculate it?

Calculate big o of function. How do I calculate the big O notation in this function?

Example: 

function fun1(int n)
{
  int s = 0;
  for(int i = 0; s < n; i++)
  {
    s += i;
    for(var j = s; j < n; j++)
      {
        console.log(j);
      }
  }
  return s;
}

Upvotes: 1

Views: 103

Answers (1)

Codor
Codor

Reputation: 17605

Roughly speaking, consider the i-th iteration of the outer loop. After execution of the loop's body,

s = 1 + 2 + ... +  i-1 + i

which is equal to i*(i+1)/2 = (i²+i)/2 by an identity by Gauss. The maximum value for i such that this expression is smaller than n is can be obtained by elementary calculation as follows. If we require

(i²+i)/2 <= n

which means

i²+i-2n <= 0

we can use the formula for reduced quadratic equation to obtain

i <= -1/2 + sqrt(1/4+2n)

which is in O(n^{1/2}). In each iteration of the outer loop, the inner loop takes n-s iterations, which very roughly can be estimated by n (but this is very imprecise, I believe the overall analysis can be made more precise). In total, this yields a bound of O(n^{1/2}*n)=O(n^{3/2}).

Upvotes: 1

Related Questions