Why the Time Complexity of Sorting a String array is O(N*S*logN) not O(N*logN)? (where N is the length of array and S is the length of the String)

Time Complexity is one of the most important thing to measure your running algorithm. When you’re giving an Interview and explains an algorithm to the Interviewer. Interviewer will definitely ask you to explain the Time/Space Complexity of that Algorithm. This is a basic concept, but many of us sometimes get confuse and may give wrong answer. Therefore, I have picked one of the concept in which we might get confused about the Time Complexity. So, let’s start….

First I’m taking Merge Sort as an example to sort an Integer/String array. And if you don’t know how Merge Sort work, I will recommend you to go through this article and understand the concepts. Here, I have written the code of sorting an Integer array using Merge Sort.

void Merge(int low, int high, int mid,vector<int> &arr)
{
    vector<int> temp;
    int i=low,j=mid+1;
    while(i<=mid && j<=high)
    {
        if(arr[i]>arr[j])
            temp.push_back(arr[j++]);
        else
            temp.push_back(arr[i++]);
    }
    while(i<=mid)
        temp.push_back(arr[i++]);
    while(j<=high)
        temp.push_back(arr[j++]);
    int x=temp.size();
    for(int i=0; i<x; ++i)
        arr[low++]=temp[i];
}
void MergeSort(vector<int>&arr,int low, int high)
{
    if(low<high)
    {
        int mid=low-(low-high)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Merge(low,high,mid,arr);
    }
}
int main()
{
    int N=10;
    vector<int> arr={3,4,7,1,3,6,9,12,2,5};
    MergeSort(arr,0,N-1);
    for(int i=0; i<N; ++i)
       cout<<arr[i]<<" ";
}

If I talk about the Time Complexity of above Algorithm, it is O(N*logN). Because we are diving our array in two halves always, therefore, the depth of the tree will always be log(N) and at every level we are doing N comparisons. That’s why the Time Complexity of sorting an Integer Array is O(N*logN) in case of Merge Sort.

But this is not the same case when we are sorting a String Array. Here, is the code of sorting a String Array using Merge Sort.

void Merge(int low, int high, int mid,vector<string> &arr)
{
    vector<string> temp;
    int i=low,j=mid+1;
    while(i<=mid && j<=high)
    {
        if(arr[i]>arr[j])
            temp.push_back(arr[j++]);
        else
            temp.push_back(arr[i++]);
    }
    while(i<=mid)
        temp.push_back(arr[i++]);
    while(j<=high)
        temp.push_back(arr[j++]);
    int x=temp.size();
    for(int i=0; i<x; ++i)
        arr[low++]=temp[i];
}
void MergeSort(vector<string>&arr,int low, int high)
{
    if(low<high)
    {
        int mid=low-(low-high)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Merge(low,high,mid,arr);
    }
}

This is completely same as sorting an Integer Array, isn’t it? But the Time Complexity of above Code is not O(N*logN). It is O(N*S*logN). The reason why the complexity has increased by O(S) is:-

while(i<=mid && j<=high)
{
   if(arr[i]>arr[j])
        temp.push_back(arr[j++]);
   else
        temp.push_back(arr[i++]);
}

The line which I have highlighted above is the reason. When we are comparing two Numbers the time is Constant, because compiler can check which number is bigger or smaller in O(1) time. But not in case of string. Let’s take an example to understand much better:

Just to give you a brief idea about how the compiler is doing comparison, I have written code. If S1= “Deepak” and S2= “Deepanjali”, then compiler can’t tell directly which one is smaller/bigger. Compiler has to compare every single character of S1 and S2 and then it can tell which one is smaller and which one is bigger. So, when compiler will compare character ‘k’ and ‘n’ , it will tell it’s result, that String S1= “Deepak” is smaller than String S2 = “Deepanjali”.

Now you know when we compare two string it doesn’t take O(1) time, it takes O(min(n,m)) where n & m are the length of the two strings.

Therefore, while sorting a String Array you should also take into account that you need to compare the strings. Each string comparison takes O(S) time(where S is length of the string).

So, There are O(N) comparisons at every level, and every comparison take O(S) time and maximum level of a tree will be log(N), therefore, this will take O( N*S*log N) time.

I hope you have learn something new today. If I missed something do tell me, in the comment box. This is my first article in medium, so, sorry for the grammatical errors.