Самый длинный общий префикс — анализ сложности подхода «разделяй и властвуй»

Я пытаюсь понять, как была получена сложность времени и пространства для подхода D & C к поиску самого длинного общего префикса из массива строк. Пример: массив строк ["leet", "leetcode", "leeds","le"] и вывод будет "le" Это проблема с leetcode 14

Код:

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);
}

Анализ сложности, как указано на их веб-сайте. Временная сложность: O(S), где S — количество всех символов в массиве, S = mn. Временная сложность равна T(n) = 2 T(n/2) + O(m). Следовательно, временная сложность равна O(S). Пространственная сложность: O(mlog(n))

Я понял ту часть, где T(n) = 2 T(n/2) + O(m), но откуда они получили m*n как временную сложность. Я думаю, что для пространственной сложности мы рассматриваем высоту дерева рекурсии, время стоимости каждого рекурсивного вызова.

n — количество строк в массиве, а m — длина префикса.