4
$\begingroup$

Assumptions

Let's say we have any recurrence relation (however this is perhaps more applicable to "unpredictable" 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 "unpredictable" 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 & m = 1\\ m^2 & 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\} & \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) &= T(n-1, 1) + T(1, m-1) + O(m + n)\\ & = \Theta(n^2 + m^2) \end{align*}$$

Improve this question
$\endgroup$
5
  • $\begingroup$ a given tree is finite size therefore you need to try to understand how the tree size varies with n... possibly using big-O notation... $\endgroup$
    – vzn
    Sep 27, 2017 at 21:56
  • $\begingroup$ @vzn, A given tree is of finite size. However, take for instance $T(n) = aT(\frac{n}{b}) + f(n)$ where $b = \texttt{random}(2,n)$ and $a = \texttt{random}(1, n)$. Perhaps even $a$ and $b$ are determined by values of the input, rather than the size. These trees are not known for a specific $n$, but perhaps the analysis of their base cases can be determined quite easily. $\endgroup$
    – ryan
    Sep 27, 2017 at 22:25
  • $\begingroup$ Hint: (1) Consider internal nodes in the tree that have a single child. (2) See if thinking about (1) suggests an extra restriction that could be added to make your desired bound hold. To prove this (more restricted) claim, try using the new condition to get upper bounds on the number of non-leaf nodes at each level, and on the number of levels. $\endgroup$
    – j_random_hacker
    Nov 19, 2017 at 12:19
  • $\begingroup$ @j_random_hacker, in general, internal nodes are not guaranteed to have a single child. Often times, no internal nodes will have a single child. Also, I'm not trying to get a bound on a particular recurrence, I'm trying to see if the implication I stated above, holds. $\endgroup$
    – ryan
    Nov 21, 2017 at 1:52
  • $\begingroup$ And I'm trying to get you thinking about a case where it clearly doesn't. Here's another hint: Consider a tree in which every internal node has exactly one child. (Note added in edit: You seem to be thinking that nodes with more than one child are the obstacle to proving your claim, but it is the single-child nodes that are this obstacle!) How many leaves are there? How many internal nodes could there be? $\endgroup$
    – j_random_hacker
    Nov 21, 2017 at 7:17

1 Answer 1

Reset to default
1
$\begingroup$

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)$:

  1. $f(n) \ll n^{\log_b a}$: in that case most of the work is done at the leaves.
  2. $f(n) \asymp n^{\log_b a}$: in that case the work done at all levels is similar.
  3. $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)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is a very good point. So for case 1 of the master theorem, this claim is clearly true because $T(n) = O(L(T(n)))$. I'm not seeing how the claim exactly relates to case 2, and maybe the claim doesn't(?) hold for case 3. Analyzing this for case 3 would be interesting. Then we must also consider the case when $a$ and $b$ are non-constant as mentioned in the original question, can we make similar claims? $\endgroup$
    – ryan
    Apr 11, 2019 at 23:56
  • $\begingroup$ The claim fails for case 3. $\endgroup$
    – Yuval Filmus
    Apr 11, 2019 at 23:58
  • $\begingroup$ Hm, I think at least conceptually, if we replace $O(\min(n,m))$ in my example above with $i \cdot (n - i) \cdot (m - i)$ we expose this behavior. Worst case of the leaves will still be as stated, but then $i = 1$ and we get $O(nm)$ work done at the root, however in the worst case we could get $\Theta(\min(n,m) \cdot n \cdot m)$ work to be done at the root. Then we would actually get much less work at the leaf level. $\endgroup$
    – ryan
    Apr 12, 2019 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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