why performance is zero for the following logic?

Question

I wrote this function for codility and got 0 in performance and 100% for correctness.

A = [-1, -3]
B = [1,2,3]
C = [1,4,5,6,77,2]

The function below is supposed to return smallest integer but not present int list passed to it.

def solution(A):
    temp = 0;
    tempLst = []
    for item in A:
        temp = temp+1
        if temp not in A:
            tempLst.append(temp)

    return min(tempLst) if tempLst else max(A) + 1

why is it so ? All I wanted is to do it without heap, itertools , partial .

Answer 1

You have what is effectively a nested loop.

for item in A:

This line loops over all elements of A.

    if temp not in A:

... and for each of those elements you loop again, comparing temp to each element of A.

The runtime of this code is quadratic in the size of A. E.g. if A has 1000 elements, this code takes 1000*1000 = 1,000,000 steps to finish.