Question:
We have an array of m strings composed of only lower case characters such that the total number of characters in all the strings combined is n.
Show how to sort the strings (in lexicographic order) in O(n) time using only character comparisons. Justify your answer.
What I have:
This really seems like it should be radix sort. Radix sort has a time complexity of O(k*(m+d)) where k is the maximum number of letters in a string contained in the array, and d is the number of "buckets" (Assuming you are using radix sort with bucket sort) in this case we know we will have 26 "buckets" (for each letter in the alphabet). Therefore we can simplify the time complexity to O(k*m).
Assuming I am correct and the best way of doing this is radix sort, what I am struggling to prove is that O(k*m) = O(n).
Am I right that this is radix sort? How can I prove that O(k*m) = O(n)?
O(k*(m+d)) ~ O(n+kd) in your case.
For example, let's say you have to sort ["ABCD", "ABDC","AB"]. When you sort the first and second character, you go through all 3 elements. But when you check for the third and fourth character, you don't have to check the string "AB" since it doesn't have a third and fourth letter. So actual times you go through each letter will be 2*3 + 2*2 = 10 which is the sum of length of all strings (plus the kd term for storing and retrieving letters).
You'll just have to tweak the radix sort by adding a few validation checks on terminated strings and it comes to O(n + kd)