Lesson 3

Below, we will see a general method for determining the growth rate of \(T(n)\) based on the constants \(a\), \(b\), and \(d\). Looking ahead, we note that \(T(n)\) will grow (at most) polynomially: the size of subproblems decreases exponentially, so the recursion tree will have logarithmic height.

Let us start with a simple example that will help us understand the general case. \[T(n)=2T\left(\frac{n}{2}\right)+n \ .\] This simplified relation describes the runtime of the merge sort algorithm (simplified because we wrote \(n\) instead of \(O(n)\)). As usual, when discussing runtimes, we assume \(T(1)=1\). This relation can be successively expanded to arrive at the solution: \[\begin{align*}T(n)&= 2T(n/2)+n=\\&=2(2T(n/4)+n/2)+n=4T(n/4)+2n=\\&=4(2T(n/8)+n/4)+2n=8T(n/8)+3n=\\&\vdots\\&=2^{k}T(n/2^{k})+kn=\\&\vdots\\&=nT(1)+\log_{2}n \cdot n=O(n\log_{2} n)=O(n\log n) \ .\end{align*}\]