3 ms·

Isn't the O(n) version actually O(NlogN) because of the sort?

by meggar 12y ago

cousin_it 12y ago
I think it only sorts the characters in each word, not the list of all words.
- meggar 12y ago
  right, but the sort was described as being O(n) for some reason.
  - aetherson 12y ago
    So 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 ago
      This 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.
nilkn 12y ago
The individual words are being sorted rather than the list of words, and N here would correspond to the number of words. The sorting of each word would traditionally be O(M log M) where M is the number of characters in the word. Note that under certain assumptions it's probably possible to sort a word faster than that because we know extra information about the elements being sorted (that is, the letters of the alphabet form a totally ordered set of small cardinality). Specifically, there exist algorithms like counting sort which exploit this extra information.

Isn't the O(n) version actually O(NlogN) because of the sort?

by meggar 12y ago

Isn't the O(n) version actually O(NlogN) because of the sort?

cousin_it 12y ago

I think it only sorts the characters in each word, not the list of all words.

meggar 12y ago
right, but the sort was described as being O(n) for some reason.
- aetherson 12y ago
  So 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 ago
    This 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.

nilkn 12y ago

The individual words are being sorted rather than the list of words, and N here would correspond to the number of words. The sorting of each word would traditionally be O(M log M) where M is the number of characters in the word. Note that under certain assumptions it's probably possible to sort a word faster than that because we know extra information about the elements being sorted (that is, the letters of the alphabet form a totally ordered set of small cardinality). Specifically, there exist algorithms like counting sort which exploit this extra information.