World's most popular travel blog for travel bloggers.

Non-integer $a$ in Master method

, , No Comments
Problem Detail: 

According to CLRS the master method requires the recurrence to be of form $T(n) = aT(n/b) + f(n)$ where $a \ge 1 $ and $b > 1$ are constants and $f(n)$ is asymptotically positive.

This makes it sound like even $a \not\in \mathbb{Z}_+$ is a legitimate value of $a$ as long as $a \ge 1$.

I have trouble visualising what kind of an algorithm would have, say, $a = 1.5$. Can anyone provide an example of an algorithm with non-integer $a$?

Asked By : ljleppan
Answered By : Hurkyl

The first thing that comes to mind would be a divide-and-conquer method where, for some reason, 50% of the time you only need to do one subproblem, and the other 50% of the time you need to do both subproblems.

The recursion for the average case runtime would be

$$ T(n) = 0.5 \cdot T(n/2) + 0.5 \cdot (2 \cdot T(n/2)) + f(n) = 1.5 \cdot T(n/2) + f(n) $$

(the fine print: this require some assumption of independence between the probability you have to do both problems and the runtime of the subproblems)

That said, the master theorem is for asymptotically solving recurrences. Not every recurrence solving problem is about the runtime of an algorithm.

Furthermore, there is no point in going out of your way to excluding cases. Insisting that $a$ is an integer doesn't simplify anything at all, so all it achieves is to make the statement (and proof too, probably) more complicated, and to frustrate those people who find a use for those cases anyways.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback