# Recurrence Equation Question

I have some difficulty trying to tell which equation to use when I'm given an explanation on how an algorithm operates. Especially divide and conquer.

Normally I see these kind of equations:

C(n) = aC(n/a) + b where a and b are constants


Other times I don't see the a in front of C(n/a) as an answer. That really confuses me.

Can you tell me when I will need to use which?

Thanks!

We can't tell you when you need to use which, since it depends on the algorithm. If the algorithm makes $a$ recursive calls to subproblems of size $n/a$, then you will see the $a$ in front. If it makes only one recursive call, then you won't see it. You need to understand what the algorithm is doing. That said, you will tend to see the $a$ in front when you are applying some operation that updates the entire list, and not see it in front when you're trying to focus on some specific element. There could also be other values other than $1,a$ in front.
• A classic example is MergeSort. This algorithm needs to sort first both halves of the array (those are two subproblems, thus a=2), and then merge them. The equation for this algorithm would be $C(n) = 2C(n/2) + n$ Oct 10 '13 at 21:24
$C(n) = aC(n/b) + c$ (and, yes, I've changed the constants) means that the cost of running the algorithm on an input of size $n$ is $a$ times the cost of running it on an input of size $n/b$, plus some constant overhead $c$. A typical case of that would be an algorithm that chops its input into $b$ equally sized parts and makes recursive calls on $a$ of those parts. Normally, you'd have $a=b$ (e.g., split the input into three and recurse on each part), which is why the formula you quoted has just two constants. But you could imagine some sort of average-case analysis where you split into some number of parts and, on average, only need to look at half of them.