How to state a recurrence equation for running time of a divide-and-conquer algorithm

Question

I'm working on my homework and I saw this problem:

A divide-and-conquer algorithm $ X $ divides any given problem instance into exactly two smaller problem instances and solve them recursively. Furthermore, whenever $ X $ divides a given problem instance of size $ n $ into smaller instances with sizes $ a $ and $ b $, then $ a + b = n $ and $ \frac 1 4 n \le a , b \le \frac 3 4 n $.

1. If the splitting and merging procedures require $ 2 n $ steps for a problem instance of size $ n $, derive the asymptotic running time $ T ( n ) $ (in $ \Theta ( ) $).
2. If the splitting and merging procedures require $ n ^ 2 $ steps for a problem instance of size $ n $, derive the asymptotic running time $ T ( n ) $ (in $ \Theta ( ) $).

I know that I have to use the master theorem after getting the recurrence equation, but I have no idea how to state the form of $ T ( n ) $. In other examples I've seen something like "it splits in three parts" which is understandable, but the $ a + b $ part makes me confused. Can someone help me please? Thanks!!

Answer 1

Well, $T(n) = T(a) + T(b) + 2n$ in the first case, with $a,b$ bounded as you mentioned

Answer 2

Let's first formulate the problem in terms of an explicit recurrence relation.

Let $ a _ 1 = a _ 2 = 1 $ and $ b _ 1 = b _ 2 = \frac 1 2 $, and consider the functions $ T , h _ 1 , h _ 2 , g $ and with the property that $$ T ( x ) = g ( x ) + a _ 1 T \big( b _ 1 x + h _ 1 ( x ) \big) + a _ 2 T \big( b _ 2 x + h _ 2 ( x ) \big) \text . $$ Also assume that $ | h _ 1 ( x ) | , | h _ 2 ( x ) | \le \frac x 4 $. Find asymptotic bounds for $ T $, when $ g ( x ) = 2 x $, and when $ g ( x ) = x ^ 2 $.

I Intentionally formulated the problem as above, so that it looks similar to the form appearing in Akra-Bazzi theorem, which is one of the best-known generalizations of the master theorem. As you can see in Leighton's note on Akra-Bazzi theorem, the given asymptotic bound by the theorem are only guarantied to work when there is some positive constant $ \epsilon $ such that we have $ | h _ 1 ( x ) | , | h _ 2 ( x ) | \le \frac x { ( \log x ) ^ { 1 + \epsilon } } $ for all large enough $ x $ (together with other requirements which hold in our problem). Unfortunately, this is not the case in our problem, and you can't use the master theorem or its well-known generalizations as you expected. But fortunately, the growth order given by the theorem works in our problem, for another simple reason. So we have a good guess using the generalized master theorem, and only need to provide a proof by ourselves. As $ p = 1 $ is the unique real number satisfying $ a _ 1 b _ 1 ^ p + a _ 2 b _ 2 ^ p = 1 $ (the critical power), the given growth order $ \Theta \bigg( x ^ p \left( 1 + \int _ 1 ^ x \frac { g ( u ) } { u ^ { p + 1 } } \ \mathrm d u \right) \bigg) $ becomes $ \Theta ( x \log x ) $ in case $ g ( x ) = 2 x $, and $ \Theta \left( x ^ 2 \right) $ in case $ g ( x ) = x ^ 2 $.

To see why the bounds work, note that both $ x \mapsto x \log x $ and $ x \mapsto x ^ 2 $ are differentiable convex functions (on our domain of interest, say $ x \ge 1 $). Thus their derivatives, $ x \mapsto 1 + \log x $ and $ x \mapsto 2 x $, are strictly increasing, and hence injective. Consider a differentiable real valued function $ f $ defined on an interval $ I = \left[ \frac n 2 - m , \frac n 2 + m \right] $ for some positive $ n $ and $ m $, such that its derivative $ f ' $ is strictly increasing. Define $ F : I \to \mathbb R $ with $ F ( a ) = f ( a ) + f ( n - a ) $. Then $ F $ is differentiable and $ F ' ( a ) = f ' ( a ) - f ' ( n - a ) $. As $ f ' $ is injective, the value of $ F ' $ can become zero only when $ a = n - a $, i.e. $ a = \frac n 2 $. Thus, as the extrema of $ F $ can only happen at the end-points of $ I $ or where the value of $ F ' $ becomes zero, we can check that for all $ a \in I $, $$ F \left( \frac n 2 \right) \le F ( a ) \le F \left( \frac n 2 - m \right) = F \left( \frac n 2 + m \right) \text , $$ or equivalently $$ 2 f \left( \frac n 2 \right) \le f ( a ) + f ( n - a ) \le f \left( \frac n 2 - m \right) + f \left( \frac n 2 + m \right) \text , $$ by determining the sign of $ F ' $. This simple observation lets us prove that our bounds work.

---

Case $ T ( n ) = T \big( a ( n ) \big) + T \big( b ( n ) \big) + 2 n $

Choose positive constants $ c _ 1 \le 2 $ and $ c _ 2 \ge \frac 1 { 1 - \frac 3 8 \log _ 2 3 } $ such that we have $$ c _ 1 n \log _ 2 n \le T ( n ) \le c _ 2 n \log _ 2 n \tag 0 \label 0 $$ for sufficiently many values of $ n $. We use (strong) induction to prove that from there on, \eqref{0} holds for all $ n $. As the induction hypothesis, assume that we have \eqref{0} for all $ n $ with $ \frac N 4 \le n \le \frac { 3 N } 4 $. Then we have $$ T ( N ) = T \big( a ( N ) \big) + T \big( b ( N ) \big) + 2 N \\ \ge c _ 1 a ( N ) \log _ 2 a ( N ) + c _ 1 b ( N ) \log _ 2 b ( N ) + 2 N \\ = c _ 1 a ( N ) \log _ 2 a ( N ) + c _ 1 \big( N - a ( N ) \big) \log _ 2 \big( N - a ( N ) \big) + 2 N \\ \ge 2 c _ 1 \left( \frac N 2 \right) \log _ 2 \left( \frac N 2 \right) + 2 N = c _ 1 N \log _ 2 N + ( 2 - c _ 1 ) N \ge c _ 1 N \log _ 2 N \text , $$ and $$ T ( N ) = T \big( a ( N ) \big) + T \big( b ( N ) \big) + 2 N \\ \le c _ 2 a ( N ) \log _ 2 a ( N ) + c _ 2 b ( N ) \log _ 2 b ( N ) + 2 N \\ = c _ 2 a ( N ) \log _ 2 a ( N ) + c _ 2 \big( N - a ( N ) \big) \log _ 2 \big( N - a ( N ) \big) + 2 N \\ \le c _ 2 \left( \frac N 4 \right) \log _ 2 \left( \frac N 4 \right) + c _ 2 \left( \frac { 3 N } 4 \right) \log _ 2 \left( \frac { 3 N } 4 \right) + 2 N \\ = c _ 2 N \log _ 2 N + \Bigg( 2 - \left( 2 - \frac 3 4 \log _ 2 3 \right) c _ 2 \Bigg) N \le c _ 2 N \log _ 2 N \text , $$ which completes the induction step.

---

Case $ T ( n ) = T \big( a ( n ) \big) + T \big( b ( n ) \big) + n ^ 2 $

Choose positive constants $ c _ 1 \le 2 $ and $ c _ 2 \ge \frac 8 3 $ such that we have $$ c _ 1 n ^ 2 \le T ( n ) \le c _ 2 n ^ 2 \tag 1 \label 1 $$ for sufficiently many values of $ n $. We use (strong) induction to prove that from there on, \eqref{1} holds for all $ n $. As the induction hypothesis, assume that we have \eqref{1} for all $ n $ with $ \frac N 4 \le n \le \frac { 3 N } 4 $. Then we have $$ T ( N ) = T \big( a ( N ) \big) + T \big( b ( N ) \big) + N ^ 2 \\ \ge c _ 1 a ( N ) ^ 2 + c _ 1 b ( N ) ^ 2 + N ^ 2 \\ = c _ 1 a ( N ) ^ 2 + c _ 1 \big( N - a ( N ) \big) ^ 2 + N ^ 2 \\ \ge 2 c _ 1 \left( \frac N 2 \right) ^ 2 + N ^ 2 = \left( \frac { c _ 1 } 2 + 1 \right) N ^ 2 \ge c _ 1 N ^ 2 \text , $$ and $$ T ( N ) = T \big( a ( N ) \big) + T \big( b ( N ) \big) + N ^ 2 \\ \le c _ 2 a ( N ) ^ 2 + c _ 2 b ( N ) ^ 2 + N ^ 2 \\ = c _ 2 a ( N ) ^ 2 + c _ 2 \big( N - a ( N ) \big) ^ 2 + N ^ 2 \\ \le c _ 2 \left( \frac N 4 \right) ^ 2 + c _ 2 \left( \frac { 3 N } 4 \right) ^ 2 + N ^ 2 = \left( \frac { 5 c _ 2 } 8 + 1 \right) N ^ 2 \le c _ 2 N ^ 2 \text , $$ which completes the induction step.