3 ms·
right, but the sort was described as being O(n) for some reason.
by meggar 12y ago
right, but the sort was described as being O(n) for some reason.
- aetherson 12y agoSo the time that is involved in this algorithm is some rough constant K * length of list * time taken to sort the average word on the list. If we were likely to see variants of the problem that scaled up both in the length of the list and the length of the words in the list, then we would properly describe the performance of the algorithm as O(n * m * log(m)), where n is the length of the list and m is the length of the longest word in the list. If, on the other hand, we assume that m is bounded and will never exceed a relatively short length (for example: because these are english words, not arbitrary character strings), then we can say that m*log(m) is essentially a constant, and the performance of the entire algorithm will vary meaningfully only based on the length of the list. That seems a reasonable assumption, so we say the performance of the algorithm is O(n).
- gamesbrainiac 12y agoThis is correct. You certainly are better at explaining this sort of stuff better than I do. If you have a blog or if you write for any org, please do give me a link, I'd sure like to improve. Let me just re-iterate your point. The longest word in the English dictionary is 45 characters long. The average is 5 and the average of the word list I've used is 8. So, when it comes down to it, saying that its constant time is a fair assumption because your (as you eloquently put it) the length of a word is bounded.