CODEWITHSUNDEEP
pythonalgorithmtime
TJarr
TJarr

Reputation: 13

Time analysis of an algorithm

I am stuck on figuring out the running time of an algorithm.

import gas

def detect_collisions(balls):
""" 
Detect any pairs of balls that are colliding.
Returns a set of ball_pairs.
"""

set_of_collisions = set()

for i in range(len(balls)):
    b1 = balls[i]
    for j in range(i):
        b2 = balls[j]
        if gas.colliding(b1, b2):
            set_of_collisions.add(gas.ball_pair(b1, b2))

return set_of_collisions

balls is a list of ball objects. and the gas.colliding() function calls a distance function which both run in constant time. I am getting n for the outer for loop (where n is the length of the balls list) and I am getting n^2 for the inner for loop because it has to run n! times I believe. Since everything else is a constant running time, this gives a time of n * n^2 or n^3. Did I go about this the right way?

Upvotes: 1

Views: 85

Answers (1)

wookie919
wookie919

Reputation: 3134

The inner for loop does not run n! times, and even if it did,n! is not equivalent to n^2.

Just work through it:

  • when i = 1, j iterates from 0 to 0
  • when i = 2, j iterates from 0 to 1
  • when i = 3, j iterates from 0 to 2
  • when i = 4, j iterates from 0 to 3
  • when i = n, j iterates from 0 to n - 1

1 + 2 + 3 + 4 + ... + n = n(n+1)/2

Thus your algorithm runs in O(n^2) time.

Upvotes: 2

Related Questions