1

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;
}
Bhavesh Odedra
  • 10,990
  • 12
  • 33
  • 58
DinhNguyen
  • 356
  • 3
  • 14
  • 1
    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
  • 1
    @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
  • 1
    @DavidEisenstat I disagree, this is a specific question about a specific piece of code. – amit Mar 25 '15 at 19:17
  • 1
    This sounds suspiciously like we're doing his homework – Populus Mar 25 '15 at 19:21

1 Answers1

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

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