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):
try:
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:
pass
else:
return -1
``````

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

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