1
$\begingroup$

If I have a recurrence equation: $$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$

It says it splits a problem of size n into 3 subproblems of size n/4. Then it keeps splitting it until the problem size at the leaves is 1 or less. The first part that does not make sense to me is how can you split a problem of size n into 3 problems of size n/4. To me it seems that there are now 3 problems of size n/4, but where is the remaining 1/4 of n? Who is solving that?

Also, the number of leaves is $$n^{\big(\frac{loga}{logb}\big)}$$ Assuming n=1000, it can be calculated that there are 235 leaves. So 235 problems of size 1 are solved, how are the rest of 765 solved?

I have a feeling that I have misunderstood some principle, but I do not know what exactly.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here is a very simple example: binary search.

We are looking for an element $x$ inside a sorted array $A$. We compare $x$ to the element at the middle $m$ of $A$. If $m = x$, we're done. If $m > x$, we recurse on the left half, and if $m > x$, we recurse on the right half. The recurrence for the worst-case running time is $$ T(n) = T(n/2) + O(1), $$ whose solution is $T(n) = O(\log n)$.

$\endgroup$
2
  • $\begingroup$ This is great! Thanks, I get the point now! Is it possible to give an example where the problem is split into more parts?(But I accept your answer either way) $\endgroup$ Jan 23, 2021 at 16:27
  • $\begingroup$ Linear time selection comes to mind: en.wikipedia.org/wiki/… $\endgroup$ Jan 23, 2021 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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