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

Question

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;
}

Do you want a broad example of what big O notation is? (and then I agree it's a dupe)? Or do you want your example being calculated and explained? (and then I disagree it's a dupe) ? — amit, Mar 25 '15 at 16:48
Oh. I want to calculate big O with simple function in this case. :) Thank u. — DinhNguyen, Mar 25 '15 at 17:05
@amit Feel free to dupe-close to this target instead: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it — David Eisenstat, Mar 25 '15 at 18:58
@DavidEisenstat I disagree, this is a specific question about a specific piece of code. — amit, Mar 25 '15 at 19:17

Codor · Accepted Answer · 2015-03-25T19:19:13.993

1

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

edited Mar 25 '15 at 19:19

answered Mar 25 '15 at 19:06

Codor

17,447
9
29
56

Did I mess something up? – Codor Mar 25 '15 at 19:09
Please prove that `sum{n-s}` is indeed `Theta(nsqrt(n))`. The O is obvious, but not the lower bound, and thus I am really not sure this bound is tight. (For example, `sum{2^i | 0 <= i <= logn}` is not `Theta(nlogn)`, please show that this phenomena does not occur in here as well, and the bound is not too relaxed. – amit Mar 25 '15 at 19:15
@amit In fact, I guess this bound is *not* tight. I'm thinking about it. – Codor Mar 25 '15 at 19:17
1

It's tight. Getting s to n/2 requires Theta(sqrt(n)) iterations, and in each iteration, we do n/2 work in the inner loop. – David Eisenstat Mar 25 '15 at 19:22
@DavidEisenstat I don't understand why we do `n/2` work in the inner loop; do you mean in each iteration or in total? If the latter, why? – Codor Mar 25 '15 at 19:26
1

@Codor Each iteration where s < n/2. – David Eisenstat Mar 25 '15 at 19:27
@DavidEisenstat Perhaps I misread something, but the inner loop's index starts at `s`, so if `s – Codor Mar 25 '15 at 19:30
1

@Codor Yes, it's an argument for the matching lower bound. – David Eisenstat Mar 25 '15 at 19:32
@DavidEisenstat Oh yes, I was confused. Thanks for the clarification. – Codor Mar 25 '15 at 19:34
@Codor: 1. "The inner loop takes n-s iterations" => I agree with you. 2. "Which very roughly can be estimated by n (but this is very imprecise, I believe the overall analysis can be made more precise)" => how can you prove that it's estimated by n. Can you interpret and explain its proving? :) – DinhNguyen Mar 26 '15 at 14:47
@CongDinh By this argument I mean `n-s <= n`. – Codor Mar 26 '15 at 15:37

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

1 Answers1