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

        if (a1 not in a):
            a.append(a1) #contains list of a0

    if (set(a) == set(y)):
        return (result, True)

    print("Not Reflexive")
    return ([] , False)

Test case:

R2 = reflexive([(1, 3), (1, 5), (3, 1), (3, 5), (7, 5)])

Not Reflexive
  • \$\begingroup\$ reflexive([(1, 1), (1, 2)]) prints "Reflexive". I would consider this a bug, since the input implies that the number 2 is an element of A and is not related to itself. \$\endgroup\$
    – mkrieger1
    Commented Jan 12, 2017 at 18:42
  • \$\begingroup\$ @mkrieger1 I believe that that is the intended behaviour, if you consider that the set A is {1}. \$\endgroup\$ Commented Jan 12, 2017 at 19:27
  • \$\begingroup\$ @200_success But then, how would I be able to use the function if I wanted to consider the sets {1, 2}, or {1, 2, 3}, where still only (1, 1) and (1, 2) were related? \$\endgroup\$
    – mkrieger1
    Commented Jan 12, 2017 at 19:35
  • \$\begingroup\$ @mkrieger1 It is pretty weird, though, that reflexive([(1,1), (2,2), (1,3)]) is True, but reflexive([(1,1), (2,2), (3,1)]) is False. I think you are right that there is a fundamental problem with the function. \$\endgroup\$ Commented Jan 12, 2017 at 20:01
  • \$\begingroup\$ @200_success That is exactly what I tried out after reading your docstring, but hesitated to post a comment, because I think I haven't understood it well enough ;) \$\endgroup\$
    – mkrieger1
    Commented Jan 12, 2017 at 20:03

2 Answers 2



It takes a very long time to conclude that reflexive((a, a) for a in range(100000)) is true. The main culprit is

if (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|)\$.


The 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 solution

I'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
    >>> essential == {(1, 1), (2, 2)}

    >>> reflexive((a, a) for a in range(100000))[0]
    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())
  • \$\begingroup\$ Wow. This is clean! I got a long way to go \$\endgroup\$
    – Joseph
    Commented Jan 12, 2017 at 19:52
  • \$\begingroup\$ Also, I didn't even notice that checking if an element is in the list was of O(n) time, like you said effectively making it O(n^2) \$\endgroup\$
    – Joseph
    Commented Jan 12, 2017 at 19:53
  • \$\begingroup\$ what is this Ohm-notation? \$\endgroup\$
    – cat
    Commented Jan 12, 2017 at 22:12
  • \$\begingroup\$ @cat Big-Omega is a stricter statement than Big-O. (Side note: I find "Big Omega" to be a funny name, since "omega" itself means "big O" in Greek.) \$\endgroup\$ Commented Jan 12, 2017 at 22:43
  • 1
    \$\begingroup\$ Why not write as result = set((a, b) for a, b in R if a == b) \$\endgroup\$
    – janos
    Commented Jan 13, 2017 at 7:08

Regardless of whether the function is actually correct or not, there are some issues that could be improved:

  1. I would expect a function that is supposed to determine whether a relation \$R\$ over a set \$A\$ is reflexive to take two arguments:

    • The relation \$R\$,
    • and the set \$A\$.

    Providing only the set \$\{(a, b) | a, b \in A, R(a,b)\}\$ and deducing \$A\$ from it is insufficient, because there could be elements in \$A\$ which are not related to any other element. This could lead to a false positive result.

  2. I would expect the function to only return a boolean value, and to have no side effects like printing its result. Leave that to the caller.

  3. The docstring of the function does not explain well enough what it expects as its argument, and does not explain at all what the function does.

  4. a and y are poorly named. What is their meaning?

  5. Instead of creating a and y a as lists to which is appended (needlessly checking if elements are already contained), only to convert them to sets at the end, why don't you just create them as sets in the first place and add to them?

  6. Parentheses are not needed around conditions in if statements:

    if a1 == a2:
    if a1 not in a:
    if set(a) == set(y):

    (also technically not around the returned tuples)

    return result, True
    return [], False
  7. This comment confuses me: What is a0?

    if (a1 not in a):
        a.append(a1) #contains list of a0

    You better just remove the comment.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.