1
$\begingroup$

Let's assume I have a list of some words found in the English dictionary: ["hat", "assume", "prepare", "cat", "ball", "brave", "help" .... ]

I want to sort these words (which are n in number) in a way, such that they are ordered based on their length, but if 2 words have the same length, they are ordered alphabetically.

What is the time complexity of this sorting operation?

Would it be fair to say that the complexity is just O(nlogn) and not take into consideration the length of the strings? If the largest length is S, can the complexity also involve a factor of S?

Improve this question
$\endgroup$
2
$\begingroup$

This algorithm requires at most $O(n \log n)$ string comparisons, assuming you use a suitable sorting algorithm.

If strings are at most $S$ characters long, each string comparison can take up to $S$ operations. So, the worst-case running time could be as large as $O(S n \log n)$.

If the size of the character set is constant, then it is possible to solve your problem in $O(n(S+\log n))$ time with a slightly different algorithm: compute the length of each string ($O(nS)$ time), sort the strings by length ($O(n \log n)$ time), then for each length, use radix sort on the strings of that length ($O(nS)$ time).

Improve this answer
$\endgroup$
0
$\begingroup$

D.W's answer gives a good and practical complexity analysis for this question.

If you really wanna analyze the complexity in terms of the memory it takes to store the entire array (as a side note, all array elements must have the same length - so instead of storing the string you store a pointer to it) and you assume the alphabet is finite and the elements in the array are unique then:

If $n$ is the number of elements, notice that defining $s$ to be the total storage the array takes, then since all elements are unique, we have that the smallest case for $s$ would have 2 elements of size 1, 4 of size 2, 8 of size 3 and so on. this means $n=\Sigma_{i=1}^k2^i=2^{k+1}-1\rightarrow k\approx log(n)$ and thus, $s=\Sigma_{i=1}^ki2^i=\Theta(k2^k)=\Theta(nlog(n)).$ Then, from that if we want to find worst case for $n$ in terms of $s$, we have $O(nlogn)=O(s)$. Now you can substitute this into any running time of an algorithm you already know.

Notice that doing this wont really help you at all! Its better to think about the complexity in terms of the number of elements $n$ instead

Improve this answer
$\endgroup$
5
  • $\begingroup$ I defined $s$ to be the total storage the array takes $\endgroup$
    – nir shahar
    Jul 2 '20 at 18:36
  • $\begingroup$ math.stackexchange.com/questions/119636/… and here is the explanation for the $nlogn$ approximation for the sum $\endgroup$
    – nir shahar
    Jul 2 '20 at 18:37
  • $\begingroup$ Sorry, I didn't read carefully enough -- you did indeed define $s$. I don't see how how you got a running time of $O(n \log n)$. None of the rest of the question justifies that the running time is $O(n \log n)$; rather it assumes that the running time is $O(n \log n)$, and then derives some consequences. The same is true of that math question. I know how to sum a series, but there seems to be a gap in your reasoning. $\endgroup$
    – D.W. ♦
    Jul 2 '20 at 18:55
  • $\begingroup$ You are right! Totally forgot about the part that comparing strings takes more time :P $\endgroup$
    – nir shahar
    Jul 2 '20 at 19:04
  • $\begingroup$ Combining it with your solution, I think you can somehow fix it $\endgroup$
    – nir shahar
    Jul 2 '20 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.