CODEWITHSUNDEEP
algorithmbig-ocomputer-science
death7eater
death7eater

Reputation: 1134

Big-O notation representation of a simple algorithm

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

Upvotes: 3

Views: 130

Answers (3)

Spektre
Spektre

Reputation: 51923

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

Upvotes: 1

Paul92
Paul92

Reputation: 9082

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

Upvotes: 3

Alma Do
Alma Do

Reputation: 37365

Your estimation comes from progression formula:

enter image description here

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

Upvotes: 5

Related Questions