Register

Recent questions tagged master-theorem

1 votes
0 answers
92
How to Solve Questions based on varients of Master Method
T(n) = a1 T(n/b) + a2 T(n/b) eg T(n) = T(n/4) + T(3n/4) + n
T(n) = a1 T(n/b) + a2 T(n/b)eg T(n) = T(n/4) + T(3n/4) + n
User Avatar
3 votes
2 answers
93
Time complexity
How to apply Master's Theorem (i) $T(n)= T(\frac{n}{2})+2^{n}$ (ii) $T(n)=2^{n}T(\frac{n}{2})+n^{n}$
How to apply Master's Theorem(i) $T(n)= T(\frac{n}{2})+2^{n}$(ii) $T(n)=2^{n}T(\frac{n}{2})+n^{n}$
User Avatar
2 votes
3 answers
94
Find complexity of T(n)=64T(n/8)-n^2lgn
Which is right method to apply for this substitute or recursion... Can we convert it in master theorem format
Which is right method to apply for this substitute or recursion...Can we convert it in master theorem format
User Avatar
3 votes
1 answer
95
Recurrence: How to approach
Solve Recurrence A) T(n) = T( √ n) + Θ(lg lg n) B) T(n) = T(n/2 + √ n) + √ 6046 C) T(n) = T(n − 2) + lg n D) T(n) = √ n T( √ n) + 100n
Solve RecurrenceA) T(n) = T( √ n) + Θ(lg lg n)B) T(n) = T(n/2 + √ n) + √ 6046C) T(n) = T(n − 2) + lg nD) T(n) = √ n T( √ n) + 100n
User Avatar
1 votes
1 answer
97
Recurrence relation
How to solve the Recurrence relation T(n)=T(n/4)+T(3n/4)+n
How to solve the Recurrence relation T(n)=T(n/4)+T(3n/4)+n
User Avatar
2 votes
3 answers
98
Master theorem details?
There are different versions of master theorem available. I want to know whether the version given in Cormen book is sufficient for GATE?
There are different versions of master theorem available. I want to know whether the version given in Cormen book is sufficient for GATE?
User Avatar
2 votes
1 answer
99
Can these be solved by Master's theorem?
1) $T(n)=T(n/2)+2^n$ 2) $T(n)=2T(n/2)+n / \log n$ 3) $T(n)=16T(n/4)+n!$ 4) $T(n)= \sqrt 2T ( n/2 ) + \log n$
1) $T(n)=T(n/2)+2^n$2) $T(n)=2T(n/2)+n / \log n$3) $T(n)=16T(n/4)+n!$4) $T(n)= \sqrt 2T ( n/2 ) + \log n$
User Avatar
0 votes
3 answers
100
Master Theorem
When do we say that 2 functions are polynomially comparable for applying master theorem...? We can apply the theorem for T(n)=3T(n/4)+nlgn but cant apply it for T(n)=2T(n/2)+nlgn ...please explain..?
When do we say that 2 functions are polynomially comparable for applying master theorem...? We can apply the theorem for T(n)=3T(n/4)+nlgn but cant apply it for T(n)=2T(n...
User Avatar
Page: