Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
