What is the order of complexity of comparing two python lists?

The complexity of comparing two lists is O(n) if both lists have length n, and O(1) if the lists have different lengths.

This very much depends on the sense of the word 'comparison'.

If you compare for equality, @Sven-Marnach's answer applies: O(n) for same length, O(1) for different lengths.

Use of a hash function can help you if you compare many lists with each other: it is O(1) for different lists (with different hashes), and may still be O(n) for lists with the same hashes since hash values may clash, and you'll have to make a real comparison. This can be alleviated by use of more than one hash function, so the probability of a clash is reduced dramatically.

Note that it still takes O(n) to compute a hash value for a list of length n, so no free lunch here.

If you want to compare two lists for similarity, you'll probably need Levenshtein distance which is quadratic in time in the straightforward case but can be made linear by lazy evaluation, probably at a great memory expense.

If you want to compute the complete list of changes to do to make one list from another (diff), it is quadratic in the best implementation mentioned in Wikipedia.