1
void function(int N){
  for (int i=0; i<N; i++)
    for (int j= 0; j< i; j++)
      System.out.println("j")
}

For this function, how does the Big O depend on the second for loop because of it being j

Also, if j < i was changed to j< N*N, Would the big O just be O(N^3) then?

Ctech45
  • 496
  • 9
  • 17
  • This is definitely an order (n^2) function. As Damien Black points out in his answer, the fact that the inner loop just increments from `0` to `i`, rather than from `0` to `N`, adds an overall constant of `1/2` but does not change the quadratic nature of the growth. – Dan Nissenbaum Jan 27 '14 at 04:44
  • possible duplicate of [Trouble Finding Big O Time for this loop](http://stackoverflow.com/questions/16986608/trouble-finding-big-o-time-for-this-loop) – Mohamed Ennahdi El Idrissi Mar 17 '14 at 22:19

2 Answers2

5

A function that loops from i = 1 to n and then has a inner loop that goes from 1 to i would go though a number of iteration equal to this formula:

n(n+1)/2

As you can see, when we get rid of everything besides the main exponent, you end with O(n^2)

If you loop from 1 to n and then have an inside loop from 1 to n^2, then yes. You are at O(n^3) because the number of iteration you go through would be equal to:

n^3

All you care about in big O notation is the largest element in the polynomial that describes the number of iterations the code will go through. The reason for this is because everything besides the largest element quickly doesn't matter as n gets larger. And we only really care about the time requirements when n is large. So an algorithm that leads to n^3 + 5n^2 + 2n iterations would have a big O notation of O(n^3).

Damien Black
  • 5,579
  • 18
  • 24
  • Why is it n^2 not (n^2)+n, because after expanding it would be (n^2+n)/2? – Ctech45 Jan 28 '14 at 01:04
  • The +n gets removed. All you care about it big O notation is the largest element in the polynomial. The reason for this is because everything besides the largest element quickly doesn't matter as n gets larger. And we only really care about the time requirements when n is large. So an algorithm that leads to n^3 + 5n^2 + 2n iterations would have a big O notation of O(n^3). – Damien Black Jan 28 '14 at 01:43
4

You can formally and straightforwardly determine the order of growth like the following:

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32