A binary relation \$R\$ on a set \$A\$ is called reflexive if and only if \$R(a, a)\$ for every element \$a \in A\$. I want to know if there can be any improvements made on the function below to make it more efficient.def reflexive(R):    '''    @param R : set containing homogenous elements    '''    result = []    a = []    y = []    for a1, a2 in R:        if (a1 == a2):            result.append((a1,a2))            y.append(a1)        if (a1 not in a):            a.append(a1) #contains list of a0    if (set(a) == set(y)):        print(Reflexive)        return (result, True)    print(Not Reflexive)    return ([] , False)Test case:R2 = reflexive([(1, 3), (1, 5), (3, 1), (3, 5), (7, 5)])Not Reflexive[]
Determining if a relation is reflexive
python;set
PerformanceIt takes a very long time to conclude that reflexive((a, a) for a in range(100000)) is true.  The main culprit isif (a1 not in a):Since a is a list, the not in test involves a linear scan, such that your entire function is \$\Omega(\left|R\right|^2)\$.  Ideally, it should be \$O(\left|R\right|)\$.InterfaceThe docstring is insufficient to describe what the function does.  In addition to a better description, I recommend adding doctests.A function like this shouldn't print anything as a side-effect.It would be more conventional to return True/False as the first element of the result rather than the second.I don't think that there is any benefit to returning an ordered list; a set would be more appropriate.Suggested solutionI'd write it this way, taking advantage of generator expressions to make it shorter.def reflexive(R):        Determine whether the binary relation R on a set A is reflexive, and if so,    which elements of R are essential for it to be reflexive.    R is an iterable of homogeneous pairs.    >>> reflexive([(1, 1), (2, 2), (3, 1)])    (False, set())    >>> is_reflexive, essential = reflexive([(1, 1), (2, 2), (2, 1)])    >>> is_reflexive    True    >>> essential == {(1, 1), (2, 2)}    True    >>> reflexive((a, a) for a in range(100000))[0]    True        R = list(R)    A = set(a for a, _ in R)    result = set(ab for ab in R if ab[0] == ab[1])    return (True, result) if len(A) == len(result) else (False, set())