Uttrakhand Asst. Professor Exam-62

Question

The running time of an algorithm $T(n)$, where $n$ is the input size, is given by following:

$T(n) = \begin{cases} 8T(n/2) + qn & \text{ if } n>1 \\  p & \text{ if } n = 1 \end{cases}$

where $p$ and $q$ are constants, the order of algorithm is

• A.  $n^2$
• B.  $n^3$
• C.  $n$
• D.  $n^n$

Answer 1

$T(n) = 8T(n/2) + qn$  if  n>1

           $= p $            if n=1

$p$ and $q$ are constants

Now, according to Master's Theorem ,

$T(n)$ = $aT(n/b) + n^c$     if $n>1$

           = $d$                if  $n = 1$

& if $log_ba$ $>c$ , then $T(n)$ = $Θ(n^{log_b a})$

 

In this recurrence relation, $a = 8$ & $b = 2$ and $c=1$

∴ $log_ ba$ = $log_ 28$ = 3

 Here, $log_ ba > c$ ,

So, order will be $T(n) = Θ(n^{log_b a})$ = $Θ(n^{3})$