Questions tagged [master-theorem]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
37 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
2
votes
2answers
86 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
1
vote
1answer
54 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...
0
votes
1answer
31 views

Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n [closed]

Could someone help me with these 2 questions? I do not understand the case 3 $T(n) = T(n/2) + n \log n$ $T(n)=T(n/8)+2 n$
1
vote
1answer
104 views

Proving recursion depth of merge sort

Hello I want to prove the recursion depth of merge sort, which is $O(\log(n))$. I think I can prove this by recurrence equation and the master theorem: $T(N)=2 T(n/2)+O(N) $ however i need to get $O(\...
2
votes
2answers
177 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
0
votes
0answers
25 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 ...
2
votes
1answer
56 views

Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log_ba}$ being polynomially smaller or ...
0
votes
1answer
68 views

Merge sort: sorting and merging complexity $\Theta(n)$

So this is the Master theorem for Merge Sort: $$ T(n) = 2T(n/2) + \Theta(n). $$ I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$. Is sorting $O(1)$ and ...
0
votes
0answers
36 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 ...
1
vote
1answer
36 views

Using master theorem to solve recurrence with log [duplicate]

I'm not sure how to solve apply the master theorem in order to solve this recurrence: $$ T(n) = 4T(n/3) +O(n\log n),\text{ where } T(1) = 1.$$ The master theorem I have been shown is normally ...
0
votes
0answers
23 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 ...
3
votes
2answers
187 views

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

I'm trying to prove that for arbitrary $c > 0$, $f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$ Intuitively, this seems to be true to me (little-o implies ...
1
vote
1answer
32 views

Proof of the master thorem case with floors and b = 2

This question is related to my previous one. Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$ and $f(n) = \Theta(n^{\log_ba})$. Then $T(n)...
1
vote
1answer
76 views

Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence ...
1
vote
0answers
31 views

Trouble with Master Theorem concerning logarithm and square root [duplicate]

I have trouble understanding how to apply the master theorem in the following problem: $$T_2(1) = 1; T_2(n) = 4T_2(2^{\log \lfloor \frac{n}{2}\rfloor}) + \sqrt{n} \text{ for } n > 1.$$ My ...
2
votes
2answers
51 views

Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$ But is it possible to use the master theorem for recurrence relations of the form $T(n) = ...
-1
votes
2answers
55 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
vote
1answer
51 views

Master theorem recurrence relation

Consider I have the following recurrence $$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$ Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get $n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2....
2
votes
2answers
135 views

Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck: $$T(n) = 2T(n/3 + 1) + n$$ I have checked out this link here on time complexity on cs.stackexchange ...
3
votes
1answer
42 views

Is there a difference between using $n$ and $\Theta(n)$ in recurrences?

Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).
1
vote
4answers
3k views

How to solve T(n)=2T(√n)+log n with the master theorem?

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?
3
votes
1answer
90 views

Master Theorem on oscillating function

Consider a recurrence of the form $T(n) = a T(n/b) + f(n)$ Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating). Suppose, however, that $f(n)$ is ...
2
votes
0answers
28 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 ...
2
votes
1answer
106 views

Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{...
1
vote
2answers
93 views

What would be the time complexity for following recurrence?

T (n) = T (n/2) + 2^n I am solving this using master theorem and I calculated it to be big theta(log2 n) (log n to the base 2). But answer state it to be 2^n. Any help would be appreciated.
2
votes
1answer
904 views

Solving $T(n)=4T(n/4)+\log n$ using master theorem

$T(n)=4T(n/4)+\log n$ I'm solving this recurrence relation by master theorem. $a=4, b=4$ , $n^{\log_b a}=n^{\log_4 4}=n$ $f(n)=\log n=O(n^{1-\epsilon})$ when $\epsilon<1$, it is correct. So, $T(...
2
votes
1answer
285 views

Regularity condition in the master Theorem in the presence of Landau notation for f

There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition ...
1
vote
1answer
997 views

Master theorem for $T(n)=T(n-1)+O(n)$

The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence $$...
0
votes
0answers
168 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 ...
0
votes
1answer
79 views

Master theorem with $T(n) = 6T(n/10) + \lg^2 n$

So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here'...
1
vote
1answer
37 views

Solving Recurrence relation with master method?

I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that? $$T(1) = c>0 $$ $$T(n) = 9T(n/3) + f(n)$$ $$f(n) = n^2\cdot lg^3 (n) +...
-1
votes
1answer
35 views

Problem in analyzing asymptotic notation in using The Master Theorem [duplicate]

As we know for master theorem: T(n)=aT(n/b)+Θ(nd) this formate is required.. But for T(n)=2T(n/2)+2^n If I want to apply theorem what will be value of d here? We cant just take d=2 here..right?
5
votes
1answer
421 views

Intuition behind the Master Theorem

The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following: For a recurrence ...
2
votes
2answers
3k views

What is the recurrence form of Bubble-Sort

I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem. As an example: The recurrence form for merge sort is ...
0
votes
0answers
722 views

Does the master theorem apply to $T(n) = 3T(n/3) + nlogn?

I am given an example of a case where the master theorem does not apply, but it seems like it should apply. This was the reasoning: $T(n) = 3T(n/3) + n log n$ with $ a = 3, b=3, f(n) = nlogn$ and ...
0
votes
1answer
93 views

Trying to solve the recurrence relation by comparing 3 cases of master theorem

I am trying to understand how the master theorem is invoked on the following recurrence relation: $$ T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}. $$ So basically, I found the following source where ...
0
votes
1answer
46 views

Master Theorem linearithmic function

I am trying to find the running time of the given recurrence by the Master Theorem: $T(n)=16T(\frac{n}{2})+n^3\log^4 n$ I get $a=16$, $b=2$ and $f(n)=n^3\log^4n$, It seems that it's Case 1 of the ...
0
votes
1answer
496 views

Solving $T(n) = 4T(n/2) + n^2log_2(n)$ [duplicate]

My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log_2^4+\epsilon})$. Otherwise, I tried solving the ...
0
votes
1answer
49 views

Master Theorem Usage

I know how to use the master Theorem for a general formula e.g. $T(n) = a \cdot T(\frac{n}{b}) + f(n)$. I saw some books suggest that we can use the mastere theorem for formulas like: $T(n) = T(\frac{...
2
votes
1answer
368 views

Why is there no regularity condition in case 1 of the master theorem?

In case 3 of the master theorem, which is applicable when most of the work is being done at the top node (roughly speaking), we also need a regularity condition that the work done at the topmost level ...
0
votes
0answers
16 views

How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n [duplicate]

I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation? T(n)= 2T(n/2) + 3T(n/5) +n
1
vote
3answers
2k views

Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
2
votes
1answer
74 views

Run time of a Simple Recurrence

Given the recurrence $T(n) = T(\sqrt{n}) + \theta(lglgn)$, provide an asymptotically tight bound on it's run time. My solution was to let $m = 2\sqrt{n}$, which leads to the recurrence $S(m) = S(m/2) ...
0
votes
2answers
471 views

Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn

I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem. At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But ...
1
vote
1answer
22 views

Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem

I have a recurrence relation: $$T(n) = 3T(\frac{n}{4}) + n\lg n$$ and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're ...
1
vote
1answer
252 views

Solving recurrence relations using substitution followed by tree method/masters theorem

$T(n) = 4T(\sqrt n) + n$ First I substitute n = $2^k$: $T(2^k) = 4T(2^{k/2}) + 2^k$ Now I rename the above as follows: $S(k)=4S(k/2) + 2^k$ Now if I try to use tree method on this in the ...
3
votes
3answers
634 views

Master Theorem: How to find the value of b in this recurrence relation

The master theorem is used with recurrences of the form T(n) = aT(n/b) + f(n) where a >=1 and b > 1, in which case the value of b can be easily seen from the ...
2
votes
3answers
5k views

Solving T(n) = 3T(n/3)+n/2 using master method

I thought I understood the Master Method quite well till I saw this question $T(n) = 3T(\frac{n}{3})+\frac{n}{2}$ My approach: $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$ $n^{\log_b{a}}$ = $n^{log_3{...
0
votes
3answers
772 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 ...