Tagged Questions

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

204 views

Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

The questions is to find the running time $T(n)$ of the following function: $$T(n)=3\cdot T(n/2) + n \tag{1}$$ I know how to solve it using Master theorem for Divide and Conquer but I am trying to ...
46 views

Applying Master Theorem to: T(n) = T(n - 2) + n^2 [duplicate]

I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation: T(n) = T(n-2) ...
12 views

Does master theorem apply differently for $n$ with restrictions? [duplicate]

Given $T(1) = 1$ and $T(n) = 4T(n/2) +n^2$ for $n\geq 2$, can I solve the recurrence for $T$ by applying the master theorem with $a = 4$, $b = d = 2$? This would give $T(n) = \Theta(n^2\log n)$.
64 views

Solving using the master theorem [duplicate]

I am wondering why this $T(n)=3T(n/4)+n⋅lg(n)$ recurrence can be solve by Master Theorem case 3 but this $T(n)=2T(n/2)+n⋅lg(n)$ recurrence can not be solve by Master Theorem what is the difference ...
20 views

Not convincing claim for Master Theorem Case 3

In a practice exam given in class, we were asked to solve the following recurrence $$T(n) = 2T(n/4) + \frac{n}{\log n}$$ The given solution claims that this falls in the third case of the Master ...
36 views

Master Theorem Case 3 Regularity Condition

In case 3 of the master theorem, we have to show that $$af(n/b) \leq cf(n).$$ I don't understand how I can setup this formula. As an example, we have $$T(n)=3T(n/4) + n \lg n.$$ In this ...
195 views

Using the Master theorem on a recurrence with non-constant a

I am trying to solve the following equation using master's theorem. $T(n) = 3^n T(\frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what ...
31 views

Time complexity of a Divide and Conquer

I have Master theorem for finding complexities but the problem is Master theorem says For a recurrence of form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$ and $b > 1$, there are following three cases:...
55 views

82 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) ...
156 views

Satisfying all the conditions of case 3 of the Master Method except the regularity condition

The regularity condition of case 3 of Master Method says that $af(n/b) < cf(n)$, for $c < 1$. How to devise a recurrence relation that satisfies all other conditions of case 3 except the ...
The master method allows us to solve certain recurrences of the form $$T(n) = aT(n/b)+f(n)\,,$$ where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further ...