CODEWITHSUNDEEP
algorithmbig-o
Tae Won Yoon
Tae Won Yoon

Reputation: 13

Is this algorithm's Big oh is n^3 rather than n^2

def triangles(A):
  n = len(A)
  result = 0
  for x in xrange(n):
    z=x+2
    for y in xrange(x + 1, n):
      while (z < n and A[x] + A[y] > A[z]):
        z += 1
      result += z - y - 1
  return result

This is an example of the solution in the codility (https://codility.com/media/train/13-CaterpillarMethod.pdf)

In the manual, they claim that the big-Oh of this algorithm is O(N^2)

Bout I think big-Oh is O(N^3) as the worst case's iteration will be

(n-1)(n-2) + (n-2)(n-3) + ..... + 1*0

so I think its big-Oh will be O(N^3).

Can anybody explain why the big-Oh of this algorithm is O(N^2)?

or am I right?

Upvotes: 1

Views: 101

Answers (2)

dfrib
dfrib

Reputation: 73186

The while loop over z will, accumulately, only run once (<n times) for each execution of the for loop over y, since z is reset only in the scope outside of the for loop over y. Hence a rough upper bound loop count of "inner scope" is along the lines n*(n+n) (which is in O(n^2)) and not n*n*n. W.r.t. calculating complexity, we might as well consider the while loop over z as a loop parallell to the for loop over y, rather than one nested within the for loop over y.

I.e., same complexity as e.g.:

def triangles(A):
  n = len(A)
  result = 0
  for x in xrange(n):
    z=x+2
    while (z < n)
      z += 1
    for y in xrange(x + 1, n):
      ...
  return result

Upvotes: 2

fgb
fgb

Reputation: 18569

For each value of x, z can only be increased up to n times. Once z is equal to n then no iterations of the inner loop is possible until x is increased again. So n values of x with n iterations of the inner loop gives n^2.

Upvotes: 0

Related Questions