Longest common prefix - comparing time complexity of two algorithms

Question

If you comparing these two solutions the time complexity of the first solution is O(array-len*sortest-string-len) that you may shorten it to O(n*m) or even O(n^2). And the second one seems O(n * log n) as it has a sort method and then comparing the first and the last item so it would be O(n) and don't have any effect on the O.

But, what happens to the comparing the strings item in the list. Sorting a list of integer values is O(n * log n) but don't we need to compare the characters in the strings to be able to sort them? So, am I wrong if I say the time complexity of the second solution is O(n * log n * longest-string-len)?

Also, as it does not check the prefixes while it is sorting it would do the sorting (the majority of the times) anyway so its best case is far worse than the other option? Also, for the worst-case scenario if you consider the point I mentioned it would still be worse than the first solution?

public string longestCommonPrefix(List<string> input) {
        if(input.Count == 0) return "";
        if(input.Count == 1) return input[0];
        
        var sb = new System.Text.StringBuilder();
        
        for(var charIndex = 0; charIndex < input[0].Length; charIndex++)
        {
            for(var itemIndex = 1; itemIndex < input.Count; itemIndex++)
            {
                if(input[itemIndex].Length > charIndex)
                    return sb.ToString();
                
                if(input[0][charIndex] != input[itemIndex][charIndex])
                    return sb.ToString();
            }
            
            sb.Append(input[0][charIndex]);
        }
        
        return sb.ToString();
    }

static string longestCommonPrefix(String[] a) 
    { 
        int size = a.Length; 
  
        /* if size is 0, return empty string */
        if (size == 0) 
            return ""; 
  
        if (size == 1) 
            return a[0]; 
  
        /* sort the array of strings */
        Array.Sort(a); 
  
        /* find the minimum length from first 
        and last string */
        int end = Math.Min(a[0].Length, 
                            a[size-1].Length); 
  
        /* find the common prefix between the  
        first and last string */
        int i = 0; 
        while (i < end && a[0][i] == a[size-1][i] ) 
            i++; 
  
        string pre = a[0].Substring(0, i); 
        return pre; 
    } 

Answer 1

First of all, unless I am missing something obvious, the first method runs in O(N * shortest-string-length); shortest, not longest.

Second, you may not reduce O(n*m) to O(n^2): the number of strings and their length are unrelated.

Finally, you are absolutely right. Sorting indeed takes O(n*log(n)*m), so in no case it would improve the performance.

As a side note, it may be beneficial to find the shortest string beforehand. This would make a input[itemIndex].Length > charIndex unnecessary.