The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
136 views

Loading Question

asked in Algorithms by Veteran (12.3k points) | 136 views
Hey guys ignore the options. What will be the answer by solving the relation?

more appropriate O(qn).

2 Answers

+2 votes

since p and q are constant ...q can have maximum constant value can go upto n....so the second part of the recurrence will give higher order .

so the order can be n^n(option b)

answered by Veteran (10.4k points)
0 votes
we can apply master theoram

a=8 b=2

k=0

a>b^k

so TC= O(n^3)
answered by Boss (9k points)
You'r doing it wrong.
Why didn't you considered term $q^n$.

Let, q = 2;

then, $T(n)  = 8*T(\frac{n}{2}) + 2^n$, which is upper-bounded by $n^n$ only.

Should not option is O(qn). since we dont take heigher value for big-oh.

question is wrong . If it was qn inplace of qn, then C is right .

otherwise O( qn) is more appropriate.

Agree O( 2n) is far far less than O(nn) . 



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

29,017 questions
36,845 answers
91,385 comments
34,723 users