how should I understand the time complexity of T(n) = 2T(n/2) + O(m) for find the longest common prefix

Question

I am studying an algorithm using divide and conquer to find the longest common prefix of n strings, with the average length of these strings being m.

The steps are:

1. recursively divide the n string to 2 groups, each has about n/2 strings, until there is only one string in a group (base case), the prefix is itself.
2. after getting the longest common prefix of 2 subgroups, merge them (find their longest common prefix) and return it to the previous level.

I did some research, and the time complexity of it is O(mn), and the recursive function is T(n) = 2T(n/2) + O(m) (from leetcode), however, I have 2 questions.

I do not know how to use the T(n) to calculate the time complexity, considering the master theory is not applicable.

use this way and find the same result, not sure if it is reasonable: in the worst case, we need to scan all the letters (mn) to find the prefixes for the deepest level, in the next level, we only need to scan half of all the letters(0.5 * mn), in the next level, we only need to scan a quarter of all the letters(0.25 * mn). So in total, we need to do mn((1/2)^0+(1/2)^1+(1/2)^2+...), so it is equal to 2mn, therefore the time complexity is O(mn).

Answer 1

One of possible ways is to write the equation like this: T(n)=T(n/2)+T(n/2)+O(m), and then imagine a binary tree, where every node T(n) has two children T(n/2). Also in every node we have O(m) - that's like a cost of splitting.

So our task is just to sum all these O(m)s. To do this we multiply them by the number of nodes.

To simplify this we can assume that n is a power of 2. In this case the lowest level of the tree will have n nodes, the next one n/2 and so on. So the total count will be n+n/2+...+1=2*n-1=O(n) like you wrote.