0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – ryan Nov 6 '17 at 18:29
  • $\begingroup$ 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? $\endgroup$ – Arun Rahul Nov 7 '17 at 1:14
  • $\begingroup$ 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)$. $\endgroup$ – ryan Nov 7 '17 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.