1 votes 1 votes Algorithms algorithms recurrence-relation time-complexity master-theorem test-series + – Rahul Jain25 asked Oct 7, 2016 Rahul Jain25 587 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Rahul Jain25 commented Oct 7, 2016 reply Follow Share Hey guys ignore the options. What will be the answer by solving the relation? 0 votes 0 votes Prashant. commented Oct 7, 2016 reply Follow Share more appropriate O(qn). 2 votes 2 votes Please log in or register to add a comment.
2 votes 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) asu answered Oct 7, 2016 asu comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes we can apply master theoram a=8 b=2 k=0 a>b^k so TC= O(n^3) cse23 answered Oct 7, 2016 cse23 comment Share Follow See all 4 Comments See all 4 4 Comments reply mcjoshi commented Oct 7, 2016 reply Follow Share 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. 0 votes 0 votes Prashant. commented Oct 7, 2016 reply Follow Share Should not option is O(qn). since we dont take heigher value for big-oh. 0 votes 0 votes Kapil commented Oct 7, 2016 reply Follow Share question is wrong . If it was qn inplace of qn, then C is right . otherwise O( qn) is more appropriate. 0 votes 0 votes Prashant. commented Oct 7, 2016 reply Follow Share Agree O( 2n) is far far less than O(nn) . 0 votes 0 votes Please log in or register to add a comment.