Consider the recurrence relation:
$\begin{array}{} T(n)& =8T \bigg( \dfrac{n}{2} \bigg) + Cn, \text{if } n>1 \\ & =b, \text{if } n=1 \end{array}$
Where $b$ and $c$ are constants.
The order of the algorithm corresponding to above recurrence relation is
- $n$
- $n^2$
- $n \lg n$
- $n^3$