Recursion Tree Analysis by Leaves Assumptions
Let's say we have any recurrence relation (however this is perhaps more applicable to &quot;unpredictable&quot; recurrence relations):
$$T(n) = \;?$$
For example:
$$T(n) = aT\left(\frac{n}{b}\right) + h(n)$$
We could have this recurrence where the input is an array of length $n$ and $a$ and $b$ are determined by particular functions of the array values (e.g. max value, min value, median value, etc.)
This is &quot;unpredictable&quot; in the sense that we do not know precisely how the tree will be structured for any given $n$.
Let's say that in the worst case the following holds:
$$T(n) = \Theta(f(n))$$
Let $L(T(n))$ be the function mapping to the total work (number of basic operations) done at the leaf level (base cases) of the recurrence relation $T(n)$. Now let's say in the worst case of $L$ (not $T$), the following holds:
$$L(T(n)) = \Theta(g(n))$$
Question
Does the following hold:
$$L(T(n)) = \Theta(g(n)) \implies T(n) = \Theta(f(n))$$
That is to say, if the work at the leaf level is worst case, does this imply that work of the total recurrence tree is worst case?

This has particular value if you don't necessarily know how the recurrence is broken up or divided throughout the tree. Perhaps you could bound the worst case work done at the leaf level and reverse engineer the tree to show the worst case overall. Alternatively, though not as useful, you may be able to prove the following:
$$T(n) = \Theta(f(n)) \implies L(T(n)) = \Theta(g(n))$$

Here is an example recurrence:
$$T(n, m) \leq \begin{cases}
n^2 &amp; m = 1\\
m^2 &amp; n = 1\\
O(\min(n,m)) + \displaystyle \max_{i \in \{1 \ldots \min(n,m)\}} \left\{ T(n - i, i) + T(i, m - i)\right\} &amp; \mathrm{otherwise}
\end{cases}$$
In this case, determining the splits is rather difficult. However, analyzing the worst case on the leaf nodes is rather simple. When we think about the recursion tree, the work at the leaves will be maximized when $n$ and $m$ are as large as possible. Namely, $T(1, m - 1) + T(n - 1, 1) = (m-1)^2 + (n-1)^2$. Now, if we know this will be the worst case overall, e.g. $$L(T(n,m)) = \Theta(n^2 + m^2) \implies T(n,m) = \Theta(f(n,m))$$
We can deduce the splits in recursion that made it this way:
$$\begin{align*}
T(n,m) &amp;= T(n-1, 1) + T(1, m-1) + O(m + n)\\
&amp; = \Theta(n^2 + m^2)
\end{align*}$$
The master theorem is a very thorough answer to this question.

Let us consider the three cases of the theorem, as applied to the recurrence $T(n) = aT(n/b) + f(n)$:


$f(n) \ll n^{\log_b a}$: in that case most of the work is done at the leaves.
$f(n) \asymp n^{\log_b a}$: in that case the work done at all levels is similar.
$f(n) \gg n^{\log_b a}$: in that case most of the work is done at the root.


Other recurrence relations behave differently. As an extreme example, there is no natural Case 1 for the recurrence $T(n) = T(n-1) + f(n)$.