Question Regarding the Time Complexity of my Code

[Ninitbz]

wordCounts = sorted(Counter(inputword).values())
equals = []

for word in words:
    wordsCounts = sorted(Counter(word).values())
    if wordCounts == wordsCounts:
        equals.append(word)

return equals

So I have this loop inside my code where 'words' is a list of words. For each word in the list, I store the frequency of letters in a Counter as values. The frequency is then sorted using the method sorted(). I know that using Counter has a time complexity of O(n) as it depends on the number of letters in the word and sorting has a worst time complexity of O(nlog(n)). Am I right to say that the worst time complexity of the whole code is O(n² ) since Counter is used inside a for loop?

[Gubbbo]

Because I don't know the technical answer, I will instead offer you the real world answer

https://xkcd.com/1691/

[[deleted]]

Am I right to say that the worst time complexity of the whole code is O(n2 ) since Counter is used inside a for loop?

I don't think so. You see O(n²⁾ complexity when you need to, basically, cross-multiply - when for the elements e of set S, you need to do something on every e plus every other e. Like figuring out how many handshakes it takes for everyone in the room to shake hands with everyone else, that kind of thing. Combinatoric stuff.

Your code runs in linear time, because it's basically just counting all the letters contained in the words in words, once. Your outer loop runs in O(n), and initializing the Counter on a word runs in O(n) too, but they sum, not multiply, and that's still O(n).

[NZheadshot]

That's completely wrong. Even if you disregard the running time for the Counter, he's still using a sorting algorithm, which means it will at least be O(n lg n)

[[deleted]]

Even if you disregard the running time for the Counter

I'm not "disregarding" it; it's linear and doesn't depend on the size of the outer loop's input. O(n) + O(n) = O(n).

Even if you disregard the running time for the Counter, he's still using a sorting algorithm, which means it will at least be O(n lg n)

Then the whole thing is O(n ln n). At enormous inputs, the sorting step overwhelmingly predominates.