Longest Common Prefix - Divide and Conquer approach complexity analysis

Question

I am trying to understand how the time and space complexity for D&C approach of finding longest common prefix from the array of strings has been derived. Example: The array of strings is ["leet", "leetcode", "leeds","le"] and the output would be "le" It's a leetcode problem 14

Code:

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

Complexity Analysis as stated on their website Time Complexity: O(S), where S is the number of all characters in the array, S = mn. Time complexity is T(n) = 2 T(n/2) + O(m). Therefore time complexity is O(S). Space Complexity:O(mlog(n))

I understood the part where T(n) = 2 T(n/2) + O(m) but from there how did they derived m*n as time complexity. For space complexity I think we are considering height of recursion tree times cost each recursive call takes.

n is the number of strings in an array and m is the length of prefix.

Answer 1

The m*n complexity comes from that O(m) term. It's replicated (executed) n times: at each iteration, you split the list in half (by quantity of strings, n), digging down until your base case gets executed once for each of the n strings. Each of those carries out an O(m) operation.

Also, each merge carries out an O(m) operation, for a total of 2*n-1 of those. 2*n-1 is O(n). O(m) * O(n) is O(mn).

Is that clear enough?