Time Complexity to sort N strings

In this article, we have explored the Time Complexity to sort N strings when each string is of length M. This is an important Algorithmic questions which most get it wrong.

Key points:

• In short, if the average length of each string is M and there are N strings, we can sort the data in O(MN logN) time in the worst case.
• If we convert the string data to integer data using a hashing technique, then the time complexity of sorting will be O(NM + N logN).
• This is in contrast to Time Complexity of sorting N numeric data is O(N logN).

Time Complexity of Approach 1: Sorting

In this approach, we use any efficient Sorting algorithm to sort String data.

Two strings of length M takes O(M) time to compare as we have to go through each character one by one.

Standard Sorting algorithms like Quick Sort take O(N logN) time for N elements.

Hence, the overall time complexity will be (MN logN) as there are O(N logN) comparisons and each comparison takes O(M) time. If we use the correct Sorting algorithm, then the time complexity will be same for all cases: worst, best and average.

Time Complexity of Approach 2: Hashing + Sorting

The downside of sorting string is that comparison takes O(M) time. This can be solved if a string is converted to an integer. This process is known as Hashing.

Hashing a string of length M takes O(M) time. So, if there are N strings each of length M, hashing all N strings take (NM) time.

Following this, the set of N numbers (converted string) can be sorted as usual. This step takes O(N logN) time.

Therefore, the overall time complexity with this approach will be O(NM + N logN). This is relatively better considering N is large such that logN becomes a key factor.

With this article at OpenGenus, you must have the complete idea of the time complexity to sort N strings.