10
votes
How to solve T(n)=2T(√n)+log n with the master theorem?
Let us actually use the master theorem.
Define $S(n) = T(e^n)$ for all $n$. Then
$$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$
Now we can apply the second case of ...
- 39.1k
8
votes
Accepted
Solving recurrence relation with square root
The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n \ge n$. So the complexity cannot be smaller than $O(n)$.
But now to your ...
- 1,585
8
votes
Accepted
Intuition behind the Master Theorem
You can use repeated substitution to obtain
$$
T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots
$$
Now suppose that $f(n) = n^\gamma$. Then
$$
\begin{align*}
T(n) &= n^\gamma + a (n/b)^\gamma + a^2 (n/...
- 278k
8
votes
How to solve $T(n)= 4T(\sqrt n) +\log^2n$?
Let $S(n) = T(2^n)$. Then
$$
S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.
$$
You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the ...
- 278k
7
votes
Accepted
Master theorem for $T(n)=T(n-1)+O(n)$
The master theorem isn't the appropriate theorem for every recurrence. As an example, your recurrence isn't of the type tackled by the master theorem, though it is easy to solve directly using the ...
- 278k
6
votes
Applying the Master Theorem on Merge sort
You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you ...
- 278k
6
votes
Accepted
Master Theorem and rounding up to the nearest integer
Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.
Why is this valid? Let me give three explanations, in order of decreasing amount of hand-...
D.W.♦
- 164k
6
votes
Accepted
Merge sort: sorting and merging complexity $\Theta(n)$
Each iteration of merge sort consist of 2 phases:
Merge Sorting the first and the second half separately.
Merging the two halves.
So in your equation phase 1 is represented by $2T(n/2)$. This means ...
- 87
6
votes
Accepted
Conditions for applying Case 3 of Master theorem
Yes, your sharp observation is completely correct.
To be compatible with the highly strict style shown at section 4.6, Proof of the master theorem of Introduction to Algorithms, here is the complete ...
- 39.1k
5
votes
Accepted
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
You are right: you can apply the Akra-Bazzi method to find that $T(n) \in \Theta(n)$.
Your professor is right: since $\Theta(n) \subseteq \mathcal{O}(n\log n)$, it is also true that $T(n) \in \mathcal{...
- 16k
4
votes
How do we derive the runtime cost of Karatsuba's algorithm?
Thank @Josiah for the question and Wiki explanation! To clearly see the runtime of Karatsuba's algorithm for the multiplication of two complex numbers by recursion with Gauss's trick, I would like to ...
- 41
4
votes
Meaning of the constants that appear in the Master Theorem
That is not the general formula for time complexity. There is no "general formula for time complexity", any more than there is a "general formula for the answer."
Rather, the formula you give is a ...
- 82.1k
4
votes
Accepted
Run time of a Simple Recurrence
First let's see how we arrive at the solution. Let's try expanding it:
$$\begin{align}
T(n) & = T(n^{\frac{1}{2}}) + \Theta(\lg \lg n)\\
& = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n^{\frac{1}{2}})...
- 4,511
4
votes
What is the recurrence form of Bubble-Sort
Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer.
Its recurrence can be written as
$$T(n) = T(n-1) + (n-1).$$
- 9,611
4
votes
How to solve T(n)=2T(√n)+log n with the master theorem?
As discussed in the other answer, the Master Theorem does not apply here.
To solve this recurrence, we can follow the similar steps in Solving recurrence relation with square root.
For $n=2^m$, we ...
- 1,046
4
votes
Accepted
Meaning of polynomially larger or smaller in the context of the master method
(This answer refers to the version 6 of the question, which does not contain "my professor's response".)
It looks like there is some typo/inconsistency/misunderstanding somewhere in your ...
- 39.1k
4
votes
Accepted
Formulating the master theorem with Little-O- and Little-Omega notation
I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log_b{a}})$ (and following the same logic, $f \in \omega(n^{\log_b{a}})$ for the third case), rather than ...
- 39.1k
4
votes
How to use Master Theorem with strange format of $b$ parameter?
Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula:
$$
T(n) = 6(n+1) + T(...
- 278k
4
votes
Accepted
Could I apply the master theorem if my $N/b$ is $\varphi(N)$?
You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem.
First, show that $\phi(\phi(n)) &...
- 2,542
4
votes
Recurrence problem T(n) = 2T(n − 1) + 1
Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$.
Method 1: Guessing
Here are some values of $T(n)$:
$$
\begin{array}{c|cccccc}
n & 0 & 1 & 2 &...
- 278k
4
votes
Accepted
Justifying a claim in the proof of the master theorem
Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the ...
- 278k
4
votes
Accepted
How can we get upper bound in terms of Big Oh notation using Master theorem?
Your reasoning is wrong. It is in $\Theta(n^{\log_2(5)})$. Hence, it is also in $O(n^{\log_2(5)})$.
Answer to the update:
Also, for the update part, it is wrong. You can find it by a straightforward ...
- 3,582
3
votes
Does the master theorem apply to T(n) = 3T(n/3) + nlogn?
Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to ...
- 133
3
votes
Trying to solve the recurrence relation by comparing 3 cases of master theorem
You determine $a$, $b$, and $f$ using pattern matching.
The Master theorem applies for recurrences of the form
$\qquad\displaystyle T(n) = a T(n/b) + f(n)$;
you have
$\qquad\displaystyle T(n) = \...
- 72.8k
3
votes
Master Theorem: How to find the value of b in this recurrence relation
You can't use the Master theorem on that function $T$.
However, as Raphael suggests, you could consider the related function
$$T'(n) = T'(n/4) + f(n),$$
use the Master theorem to find a solution ...
D.W.♦
- 164k
3
votes
Accepted
Solving $T(n)=4T(n/4)+\log n$ using master theorem
Let's use the other method to solve recurrences, namely, repeated substitution, assuming that $n$ is a power of 4:
$$
\begin{align*}
T(n) &= \log n + 4T(n/4) \\ &=
\log n + 4 \log(n/4) + 16T(n/...
- 278k
3
votes
Accepted
Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$
If we are not restricted by "using the master theorem", then either a better version of the master theorem, the versatile Akra-Bazzi method or the elementary way to show many recurrence relations mean ...
- 39.1k
3
votes
Accepted
$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$
This is false. Consider for example
$$ f(n) = \frac{n^c}{\log n}. $$
- 278k
3
votes
Accepted
Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$
As mentioned by @Yuval Filmus in the comment, you can use the extension of the master theorem (case 2b). The result is $T(n) = \Theta(n^2 \log\log{n})$.
- 3,582
Only top scored, non community-wiki answers of a minimum length are eligible