uneven-split recurrences

Not every recursive algorithm cuts its input into equal halves. Quicksort with a bad pivot might split n into a piece of size 1 and a piece of size n-1; the median-of-medians selection splits into pieces of size n/5 and 7n/10. When the children have DIFFERENT sizes, the recurrence is 'uneven', and the neat Master Theorem (which assumes every subproblem is n/b) no longer fits.

An uneven-split recurrence looks like T(n) = T(alpha n) + T(beta n) + f(n) with alpha and beta different (and possibly more terms), or T(n) = T(n/5) + T(7n/10) + Theta(n). The recursion tree becomes lopsided: branches of different depths, leaves at different levels. You can still reason about it. A useful first move is to sum the fractions: if the total fraction of work passed down is less than 1 (e.g. 1/5 + 7/10 = 9/10 < 1), the per-level work shrinks geometrically and the top level f(n) tends to dominate, often giving Theta(f(n)). If the fractions sum to exactly 1 with constant-time combine you frequently get linear or near-linear behaviour. For exact answers you use the Akra-Bazzi method, which is built precisely for unequal b_i.

These recurrences matter because uneven splits are common and sometimes deliberately engineered: median-of-medians chooses the 1/5 and 7/10 sizes so that 1/5 + 7/10 < 1, which is exactly what forces linear time. The honest warning: intuition about 'roughly balanced' can mislead. T(n) = T(n/3) + T(2n/3) + n actually costs Theta(n log n) (the fractions sum to 1, so it behaves like a balanced split), while T(n) = T(n/5) + T(7n/10) + n costs only Theta(n) — small changes in the split fractions change the asymptotics, so compute, do not guess.