TTomasik TTomasik -4 years ago 179
Python Question

Python - time complexity O(N**2)

can anyone tell me where in code below, we get O(N**2):

def solution(X, A):
assistant = list(range(1, X+1))
assistant_sum = sum(assistant)
helper = set()
if X not in A:
return -1
if A.count(A[0]) == len(A):
if A[0] == 1:
return 0
return -1
for y in A:
sorted_helper = sorted(list(helper))
if sum(sorted_helper[0:X]) == assistant_sum:
helper = set()
for index, i in enumerate(A):
if len(list(helper)[0:X]) == len(assistant) and int((list(helper)[0]+list(helper)[X-1])/2.0*len(helper)) == assistant_sum:
return index
except IndexError:
return -1

Is there any way to check time-complexity online?
Thanks for help!

Answer Source

helper is a set which can be up to the same length as A. in your for loop for index, i in enumerate(A) you are then calling list(helper)

With the length of A being N, list(helper) is O(N), for index, i in enumerate(A) is O(N).

A statement of O(N) inside a loop of O(N) gives O(N**2)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download