edited by
2,067 views
1 votes
1 votes
which of the following cannot be solved using masters theorem?

a) T(n) = 2T(n/2) + n/logn

b) T(n) = 2T(n/2) + logn

c)T(n)=T(n/2)+logn

d) non of these
edited by

2 Answers

1 votes
1 votes
General form of master's theorem -

T(n)=aT(n/b)+Q(n^k (log^p)n)

where a>=1,b>1,k>=0 and p is real.

according to this all are satisfied so ans is D.
1 votes
1 votes

 

Inadmissible equations

The following equations cannot be solved using the master theorem:

  • a is not a constant; the number of subproblems should be fixed

  • non-polynomial difference between f(n) and  (see below; extended version applies)

  •   cannot have less than one sub problem

  • f(n), which is the combination time, is not positive

  • case 3 but regularity violation.

In the second inadmissible example above, the difference between  and  can be expressed with the ratio . It is clear that  for any constant . Therefore, the difference is not polynomial and the basic form of the Master Theorem does not apply. The extended form (case 2b) does apply, giving the solution .

I have completely copied this portion from wikipedia https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

and from the second inadmissible equation, it is clear that the correct answer is A

Related questions

2 votes
2 votes
1 answer
1
2 votes
2 votes
1 answer
2
0 votes
0 votes
0 answers
3
rexritz asked Aug 13, 2023
294 views
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
0 votes
0 votes
1 answer
4
lucasbbs asked Feb 28, 2022
6,574 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...