4

The questions is:

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

The solution is given as below: enter image description here

What i find peculiar in the above solution is this: "You should also take into account that you need to compare the strings. Each string comparison takes O (s) time.There are O (a log a) comparisons, therefore this will take O (a*s log a) time."

What do we need the comparisons for?

It would take s log s time to sort a string. Say there a strings hence the total time taken would be a*s log s

Now the problem has shrunken down to simply sorting a given array which you can do in a log a time, hence the total time taken is a*s log s + a log a = a (s log s + log a)

Where did I go wrong in my thought process?

The question is taken from the book, Cracking The Coding Interview

Improve this question
2
  • Each string comparison takes O(s) time. That's the part you missed while reasoning. Comparing two char takes O(1), comparing two strings takes O(length(shortest string)). Commented May 27, 2019 at 9:25
  • 1
    The claim that "There is no way to reduce it further" seems to stretch it. It's clear that a trivial string comparison will be O(s) - but it doesn't immediately follow that the string sorting in this case must be implemented in that way. Commented May 27, 2019 at 16:30

1 Answer 1

Reset to default
4

Sorting a list of numbers assumes that comparisons occur in O(1) constant time, giving the nlogn complexity, in terms of number of comparisons. However when we are sorting an enumerable whose members require a time x to compare,the run-time becomes xnlogn. This is because we are performing an action that requires x time, nlogn times.

But, I must also argue, that strings are a direct bijection to base 26. Since we consider comparison in base 10 to occur in constant time, there is no reason not to extend this to the strings which are essentially numbers in base 26. This really depends on the implementation of the string comparing mechanism. So, depending on how string comparison is done, we end up with two possible runtimes.

Yours is correct, if and only if we assume strings to be compared as numbers in base 26, and assuming that can be done in constant time.

Otherwise, sorting in general takes (Comparison time) x nlogn

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Related: How can we assume that basic operations on numbers take constant time? The same argument doesn't really apply to strings.
Sorting complexity is typically given in terms of the number of comparisons (for comparison-based sorting, at least). There doesn't need to be any assumption about the complexity of a single comparison in that case. Although the ultimate conclusion is the same.
They're asking for time, not number of comparisons. While time is arbitrary, they seem to want something in terms of lengths of the individual strings. Furthermore, I didn't really understand the related link, but I don't see any reason for this assumption not to apply to strings, given implementation of strings as character arrays, which are essentially integer arrays, as mentioned in the question
Numbers are most commonly 64 bits or less, and many operations can be done in parallel and check or process all the bits anyway, so their running time is often not dependent on the exact number of bits the number occupies. Strings, on the other hand, don't have a common fixed upper length limit, a comparison would involve checking one position at a time and it's running time is very much dependent on the exact length of the string. But there may be some handwaving, since you can't strictly speaking say a constant space number can represent the length of something that's variable space.
I see. Assuming a string to be a number without upper bounds, then we can take its compare time to be (length/parallel processes)?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.