# Questions tagged [master-theorem]

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

163 questions
Filter by
Sorted by
Tagged with
1answer
81 views

3answers
2k views

### Meaning of the constants that appear in the Master Theorem

The general formula for time complexity is $T(n) = aT(n/c) + bn^k$. If $a> c^k$, the complexity is $O(n^{\log_c a})$. If $a = c^k$, it is $O(n^k \log n)$. If $a < c^k$, it is $O(n^k)$. $a$ is ...
1answer
2k views

### Applying the Master Theorem on Merge sort

I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into ...
0answers
9 views

### Need Help solving Recurrence Problem [duplicate]

I have this practice problem that I was given. I am trying to solve a specific recurrence equation T(n) = 4 when n <= 2 T(n) = 3T(n/3) + 5 when n > 2 ...
1answer
626 views

2answers
459 views

### Usage of master theorem for solving recursions

I know that master theorem is used for the recurrence relations of the form: T(n) = aT(n/b) + f(n) But in my question, i am supposed to solve the following recurrence relation by using master ...