-4
    for(int i = 0 ; i < n ; i++) { 
        a[i] = scan.nextInt();
    }
    for(int i = 0 ; i < n ; i++) {
        for(j = n ; j >= 0 ; j--)
            a[j] = a[j] + a[i];
    }

I cant seem to properly find the time complexity of the code or convert to big O. I know the first loops is 1 + (n+1) + 1 and i think the 2nd/3rd ones are N*(1 - (N-1) * 1)

Nir Alfasi
  • 53,191
  • 11
  • 86
  • 129
Vymahesh
  • 1
  • 1
  • 1
    Please indent your code sensibly. – President James K. Polk Oct 12 '17 at 22:50
  • 5
    *"I know the first loops is 1 + (n+1) + 1"* Then please forget what you know because it is wrong. The first loop iterates `n` times, so the first loop is _O(n)_. Second (outer) loop also iterates `n` times. Third (inner) loop iterates `n+1` times. So, the nested loops are _O(n²)_. – Andreas Oct 12 '17 at 22:51
  • 1
    first one is O(n), second one is O(n^2) – Irwan Hendra Oct 12 '17 at 22:53
  • 1
    You might find [A plain English explanation of "Big O" notation](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) a useful read. – azurefrog Oct 12 '17 at 22:55

1 Answers1

3

The O(n) notation is the degree of the largest term in the polynomial describing the code, and describes how the time to run grows as the input size increases.

Therefore, small details such as coefficients and lower order terms are unimportant.

Since there are two nested for loops that both iterate once through the input (size n), the code is O(n^2). The single for loop is O(n) and is not the highest order term, so it is dropped.

Evan Weissburg
  • 1,564
  • 2
  • 17
  • 38