How can recursion tree split a problem into smaller pieces that do not add up? 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.
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 &gt; x$, we recurse on the left half, and if $m &gt; 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)$.