Big-O notation representation of a simple algorithm

Question

How can I represent its complexity with Big-O notation? I am little bit confused since the second for loop changes according to the index of the outer loop. Is it still O(n^2)? or less complex? Thanks in advance

for (int k = 0; k<arr.length; k++){
      for (m = k; m<arr.length; m++){
           //do something
      }
}

Answer 1

Your estimation comes from progression formula:

and, thus, is O(n^2). Why your case is progression? Because it's n + (n-1) + ... + 1 summation for your loops.

Answer 2

If you add all iterations of the second loop, you get 1+2+3+...+n, which is equal with n(n+1)/2 (n is the array length). That is n^2/2 + n/2. As you may already know, the relevant term in big-oh notation is the one qith the biggest power, and coeficients are not relevant. So, your complexity is still O(n^2).

Answer 3

well the runtime is cca half of the n^2 loop

• but in big O notation it is still O(n^2)
• because any constant time/cycle - operation is represented as O(1)
• so O((n^2)/2) -> O((n^2)/c) -> O(n^2)
• unofficially there are many people using O((n^2)/2) including me for own purposes (its more intuitive and comparable) ... closer to cycle/runtime

hope it helps