note PA2

To calculate \(T(n) \ (n > 1)\) with \(\log_2 n\) equations. \begin{eqnarray} T(n) &=& a + 2T(n/2) + bn \\ 2T(n/2) &=& 2a + 4T(n/4) + bn/2 \cdot 2 \\ 4T(n/4) &=& 4a + 8T(n/8) + bn/4 \cdot 4 \\ &\vdots& \\ n/2 T(2) &=& an/2 + nT(1) + bn \end{eqnarray} Therefour, \(T(n) = a(1 + 2 + \cdots + n/2) + nT(1) + b(n + n + \cdots + n) \). Denote \(A(n) = a(1 + 2 + \cdots + n/2)\) \(B(n) = b (n + n + \cdots +n) \) \(A(n) < a(n + n + \cdots + n) = an \log_2 n\) \(B(n) = bn \log_2 n \in \Theta(n \log n)\) and \(A(n) < B(n)\). \(T(1)\) is a constant, then \(T(n) \in \Theta(n \log n)\) Then, \(T(n) \in \Theta(n)\).