0
$\begingroup$

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!

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Oh, ok. I know examples of those without the a in front include binary and ternary searches. But what is an example of one that does have it? $\endgroup$
    – Julio Garcia
    Oct 10 '13 at 17:43
  • 2
    $\begingroup$ 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$ $\endgroup$
    – ees_cu
    Oct 10 '13 at 21:24
3
$\begingroup$

To use any formula, you need to think about what it means. You can't just blindly apply formulas.

$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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.