The Gateway to Computer Science Excellence
+1 vote
867 views
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
in Algorithms by
edited by | 867 views

3 Answers

+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 = n3

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

by Boss
edited by
0 votes
answer given is n3 i.e,(c) but not know the reason
by
+1

Using master theorem ans is n.

i.e. nlog2= n> n2

0
Thanks vkm for updating question clearly now!!
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).

by Active

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,222 questions
59,846 answers
201,030 comments
118,094 users