How does Python sort() time complexity change with lambda functions with non O(1) complexity?

Question

I have an array 'logs', where logs = ["1 art can", "2 own kit dig", "3 art zero", "4 art can"]. Each element is a string which has a serial number, followed by a bunch of words. I need to sort the array in the lexicographical order of the string contents (excluding the serial number). If two strings in the array have the same content, I need to sort them based on their serial numbers.

I used the sort() function in combination with a lambda function which in turn uses the split() function. Usage below: logs.sort(key=lambda x: (x.split()[1:], x.split()[0]))

I know that the time complexity of sort() is O(nlog(n)) and split() itself has a O(n) time complexity. Assuming there are n strings, each of length m, what is the effective time complexity of logs.sort(key=lambda x: (x.split()[1:], x.split()[0]))?

Answer 1

According to the documentation (emphasis mine):

Both list.sort() and sorted() have a key parameter to specify a function to be called on each list element prior to making comparisons.

So all the keys are computed once, not while doing all the comparisons. The complexity of performing all the key computations is added to the complexity of the sorting. So the overall complexity will be whichever has the larger order.

Answer 2

A single pass is done and the key function (the fact that you use a lambda expression is completely irrelevant) is applied once to each element. So that operation is O(m*n) where m is the maximum size of each string and n is the size of the list. However, if we assume m is small or non-varying, we can just say it's O(n) and the overall algorithm stays O(n*log n).

Suppose instead, though, you had a list and you want to sort the items by their frequency. And you naively do

sorted(mylist, mylist.count)

Well now the application of the key function is O(n**2) on the size of the list. The sorting itself is still O(n log n), but now your overall algorithm is O(n**2)

Note, one way to avoid the above would be to do

sorted(mylist, Counter(mylist).get)

Using a collections.Counter object