# Questions tagged [master-theorem]

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

31 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
219 views

• 21
88 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 ...
• 152
1 vote
20 views

### Is this a special case of a recurrence where the Master Method is not applicable?

So in an exam, this was the recurrence: $$T(n) = 2T(n/2) + n log(n) -n + O(log(n))$$ $$T(1) = 1$$ Why does the master method not apply here? I think it is indeed int he form $$aT(n/b) + f(n)$$ You ...
• 31
1 vote
31 views

• 111
23 views

137 views

### How to find running time complexity of divide and conquer method without Master Theorem

I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
220 views

### Master Theorem Help - How to make the value of "b" greater than 1 as required by the Master Theorem? What math is involved?

I know how to identify the parts of the Master Theorem, and I know that it is a recurrence relation. I don't understand how to make the "b" value greater than 1. Please see the image. I know the math ...
211 views

### Finding runtime of a recurrence relation with a fractional power

Consider the following algorithm and find the tightest Big-$O$: Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$. If my runtime is $T(n)$, I have: Lines 1 ...
• 275
31 views

### The applicability of the Master Theorem and calculation of asymptotic limits

Given the following recursive equation $T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$ I want to know how to explain the applicability of the Master theorem in a rigorous way and what means asymtotic limits of ...
702 views

### How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has. I usually ...
• 23
I have the following recurrence: $F(n, L) = 2F(n / 2, L) + nL + n^2 log(n)$. Am I correct in saying that $F(n, L) \in O(n \log(n) L + n^2 log(n))$? I got to this result by bounding the $nL$ and n^2 \... -1 votes 2 answers 129 views ### Using Iterative method to find recurrence relation vs Master Theorm I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem. \begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &=... -1 votes 1 answer 340 views ### A difficult master theorem problem Consider the function B:\mathbb{N}\rightarrow\mathbb{R} defined by B(n) = \begin{cases} 1 &\text{ifn\le 2}\\ B\left(\left\lceil\frac{n}{\log_2n}\right\rceil \right)+n&... • 11 -1 votes 2 answers 123 views ### Divide and conquer recurrence relation I have divide and conquer problem and below is the recurrence relation for it \begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\ t(n) &= a\cdot t (n/4) + O(n^2) \end{align} ... -1 votes 1 answer 197 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) ... -3 votes 1 answer 70 views ### How to solve T(n)=2T(√n)+(loglogn)^2? Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part -3 votes 1 answer 67 views ### Solve the recurrence3T(n) = T(n/3)+ \sqrt{\log n}\$
How can you solve the recurrence $$3T(n) = T(n/3)+ \sqrt{\log n}$$ using the master theorem? I am lost in this question.