Using master theorem ans is n^{3 }.

i.e. n^{log28 }= n^{3 }> n^{2}

The Gateway to Computer Science Excellence

+1 vote

The running time of an algorithm T(n), where ‘n’ is the input size, is given by— T(n)=8⌈(n/2)+qn,if n>1⌉=p,if n=1

where p, q are constants. The order of this algorithm is—

(a) n2 (b) nn

(c) n3 (d) n

where p, q are constants. The order of this algorithm is—

(a) n2 (b) nn

(c) n3 (d) n

+1 vote

Thank you @Anirudh sir for the correction..!! //Question was not clearly typed before. Thank for updating :)

Assuming that the question given is T(n )= 8 (n/2) + qn

n ^{log 2 8} = n^{3}

and using Masters theorem, T(n) = Θ(n ^{3} )

0 votes

0 votes

$T(n)=8T(\frac{n}{2})+qn$

Using master's theorem, we'll compare this will the standard formula:

$T(n)=aT(\frac{n}{b})+\theta(n^klog^pn)$, we find that

$a=8, b=2, k=1,p=0$, and $a>b^k$

The Order of the recurrence becomes

$\theta(n^{log_ba})\rightarrow\theta(n^{log_28})=\theta(n^3)$

Option **(C).**

52,222 questions

59,846 answers

201,030 comments

118,094 users