NIELIT 2017 OCT Scientific Assistant A (CS) - Section C: 4

Question

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

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

$ = p,$ if $n = 1$

Where $p,q$ are constants. The order of this algorithm is

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

Comments

Use back substitution.

---

Manually means by using the tree approach. Just as we do forr merge sort.

---

bro, actually we are not dividing the input size of n into 8 parts.

here ,  a function takes an input of size of  n , and by definition of the the above  recur. relation  it calls 8  function of  its type but here with size  = n/2.

and, subsequently each of these call 8 funtion of size= n/4.

and  for every level calling cost = (n).

hope yu understand.

Answer 1

We can directly apply master’s theorem on this to get T(n).

T(n) = aT(n/b)+ f(n) a>=1, b>1
and
If f(n) is Ɵ(n^d) d>=0

then,
if a<b^d then T(n) = Ɵ(n^d)
elif a==b^d then T(n) = Ɵ(n^d logn)
elif a>b^d then T(n) = Ɵ(n^(logab)

Here,

a = 8; b = 2; d = 1

and, a>$b^{d}$

Therefore,

T(n) = Ɵ(n$\log_{a} b$) = Ɵ(n$\log_{2} 8$) = Ɵ($n^{3}$)