GATE CSE
First time here? Checkout the FAQ!
x
0 votes
103 views

Loading Question

asked in Algorithms by Boss (7.3k points)   | 103 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 Boss (9.5k 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 (8.2k 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) . 

Top Users Feb 2017
  1. Arjun

    5234 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3828 Points

  4. Aboveallplayer

    3006 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2148 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1628 Points

Monthly Topper: Rs. 500 gift card

20,841 questions
26,000 answers
59,638 comments
22,072 users