# Questions tagged [master-theorem]

Questions on the Master theorem, a method for obtaining asymptotic bounds on recurrences of a specific form.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0answers
205 views

0answers
37 views

### Reference request: Leaf-heavy master theorem algorithms

I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication. Are there other recursive ...
1answer
42 views

### Using inductive hypothesis on recurrence relation?

I have a recurrence relation as follows $$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$ Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
0answers
127 views

### Advanced Master Theorem?

I have learned the Master's Theorem from the CLRS textbook (2nd Edition), the form of the Master Theorem given in the above text is associated with the proof of each and every case. So at the end I ...
0answers
107 views

### How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I want to solve the following using master theorem. $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$ I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$ I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$ I ...
0answers
132 views

1answer
170 views

### Master Theorem Questions?

NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie. State the asymptotic (worstcase) ...