Doubt - Source : Stack_Overflow

Question

How the case is matched  ? :

 

T(n) = 2T(n/2) + O(n * m)

we have a = 2, b = 2, c = 1 and c = $Log_ba$  (case 2)

Hence, T(n) = O(n * m * log n)

Now, substituting m with n

T(n) = O(n2 * log n)

Comments

What is m here ? if not a constant what is the range of it ?

---

@Hemanth_13 

 

The problem is :

" A list of n strings each of length m is sorted into lexicographic order using the merge sort algorithm. The worst case running time of this computation is? "

Now, these "m" elements also not sorted then , will we again use divide and conquer on separate lists of m elements each after dividing these "n" lists ?

 

Above question explain what is "m' .

P.S.: just help me in mastet method

---

take m length strings and apply merge routine

take two-two strings of m length and apply merge routine one time --> in worst case O(nm)

now take 4 strings -> O(nm)

8 strings-->O(nm)

16 strings -> O(mn)

similarly if we proceed all n strings --> O(nm)

here the merge routine is applied $logn$ times.

Total time complexity = $O(mn)*logn$===> $O(mnlogn)$

---

@Hemanth_13 

I am aware of conventional method of solving this. But i have posted this to know how that Master's Method is performed.