# Practical example for recurrence relation of merge sort with more than 2 sublists

I couldn't wrap my head around for finding an example for the following recurrence.

$T(n) = a T(n/b) + f(n)$ where $a \neq b$ and $b > 1$

If we divide n elements with b, it should give us a sublists each with size n/b

Could somebody please give me a practical example of this?

• What do you mean by "practical"? You could trivially make $a>b$ by repeating some recurrences. You won't be able to get $a<b$ because that would break the $n\log n$ lower bound if $f(n)=\Theta(n)$. Alternatively you could increase $f(n)$ to get $a<b$. Can you give a better description of "practical", because there are many ways to do this.
– ryan
Nov 6 '17 at 18:29
• Consider any divide-and-conquer algorithm like Merge-sort. Let us say I have 12 elements which is n. Lets us say b is 4. Then we get 3 sublists each of size 4. But, as I said in the question, 4 is not $n/b$. Am I confused here? Nov 7 '17 at 1:14
• An example of how to multiply two $n$-bit integers is Karastuba's Algorithm which has recurrence relation $T(n) = 3T(n/2) + cn$. Another example is Strassen's Algorithm for matrix multiplication which has recurrence relation $T(n) = 7T(n/2) + \Theta(n^2)$.
– ryan
Nov 7 '17 at 1:26