Order and run time of the algorithm?

Question

Running time of an algorithm $T(n),$ where $n$ is input size is given by

$T(n) = \begin{cases} 8 T(n/2) + qn, & \textsf{ if } n>1 \\  p, & \textsf{ if } n=1 \end{cases}$ where $p$ and $q$ are constants. $T(n)$ is 

• A. $\Theta(n^2)$
• B. $\Theta(n^n)$
• C. $\Theta(n^3)$
• D. $\Theta(n)$ 

Answer 1

Case 1 of master theorem as

$f(n) = O\left(n^{\log_b a -\epsilon} \right ) \\= O\left(n^{\log_2 8 -\epsilon }\right) \\= O\left(n^{3 -\epsilon} \right)$

is true for any $ 0 < \epsilon \leq 2$.

Now, the complexity is $\Theta\left(n^{ \log_b a }\right) = \Theta \left(n^3\right)$.