16
In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side, leaving us with something that looks like $U(n) = U(\sqrt{n}) + something$. In this case, things work out very nicely:
$$\begin{align}
T(n) &= \sqrt{n}\ ...
11
Throughout this answer, we assume $f$ and $T$ are non-negative. Our proof works whenever $f = \Theta(g)$ for some monotone $g$. This includes your Mergesort example, in which $f=\Theta(n)$, and any function which has polynomial growth rate (or even $\Theta(n^a \log^b n)$).
Let's consider first the case that $f$ is monotone non-decreasing (we'll relax this ...
8
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 computation. Setting $n=2^m$, we obtain as you did
$$ T(2^m) = T(\sqrt{2 ^ m}) + 2^m=T(2 ^ {\frac{m}{2}}) + 2^m.\tag{1}\label{eq1}$$ You defined $$S(m) = T(2^m)....
7
No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you break into two sub-problems of the same size ($b=2$), but only recurse on one of them ($a=1$). In this case, the recurrence would look like: $$T(n) = T(n/2) + O(1)\...
7
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 the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain
$$ S(n) = \Theta(n\log n)$$
So for $n\gt0$,
$$ T(n) = S(\log n) = \Theta(\log n \log\...
6
This is not solvable using (only) the Master Theorem. It's not in the correct form. The Master Theorem only applies when there's a constant in front of the $T(n/b)$, and $3^n$ is definitely not a constant.
You should try calculating a bound for $\log(T(n))$ instead. Even though that won't give a tight bound it will get you on the right track.
6
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-waving:
Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$...
6
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 can split it into two arrays of length at most 2.5. But you are able to split it into two arrays of length at most $\lceil 2.5 \rceil = 3$.
Note that the ...
6
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 well-known identity
$$ \sum_{i=1}^n i = \frac{n(n+1)}{2} = \Theta(n^2). $$
You should think of the master theorem as a tool, not a liability. It is supposed to ...
5
As Rick Decker mentions, in this context $\log^p n = (\log n)^p$, and so $p$ can be an arbitrary real number. If you wanted to denote composition, you would use $\log^{(p)} n$ (which in other contexts signifies the $p$th derivative!). In that case, when $p$ is a negative integer, you just need to use the inverse of $\log$, namely $\exp$:
$$
\begin{align*}
\...
5
OK, try Akra-Bazzi (even if Raphael thinks it doesn't apply...)
$$
T(n) = 4 T(n / 2) + n^2 / \lg n
$$
We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a_1 = 4$, $b_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h_i(n)$ also check out. So we need:...
5
You may solve this recurrence by using the Akra-Bazzi method, which generalizes the master theorem and allows solving recurrences of the form
$T(n)= \sum\limits_{i = 1}^k {a_i T(n/b_i) + f(n)}$
You need to solve for $p$ the equation
$\sum\limits_{i = 1}^k {a_i b_i^{-p} = 1}$
and the solution to the recurrence can be obtained exactly as in the master ...
5
Try this way:
$$
\begin{align*}
T(n) &= T(n/2) + n^2 \\
T(n) &= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\
T(n) &= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)}
\end{align*}
$$
You will end up with:
$$
\begin{align*}
T(n) &= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\
T(n) &= n^2 + n^2/4 + n^2/16 + ...
5
Take a look at Tom Leighton's notes, referenced from the Wikipedia article.
His notes apparently have less typos then the original paper. The condition he demands of $g$ is having polynomial growth, which means that if you scale the argument by a constant, then the amount that the function scales is also bounded by a constant.
5
I suppose you are looking for an asymptotic bound. Notice that the recursion depth is $\log^* n$, that is how often do I have to apply the logarithm recursively to get below 2. Also, the function is increasing. Using these two facts, you can plug in the recursion once and then you see that you have at most $\log^*$ summands, each of them at most $\log^2 n$ ...
5
There are several different versions of the Master Theorem. This situation is common in mathematics: a well-known theorem may have several common versions, for example the Chernoff–Hoeffding bound(s). Perhaps one version is the original, and another is a widely known strengthening; or perhaps one version is the original, and another is the one appearing in ...
5
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/b^2)^\gamma + \cdots \\ &=
n^\gamma \left[ 1 + \frac{a}{b^\gamma} + \left(\frac{a}{b^\gamma}\right)^2 + \cdots \right].
\end{align*}
$$
Let us assume that ...
5
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 that merge sort is called on the two halves. This is a recursive call, which is why $T$ is used here.
Phase 2 is represented by $\Theta(n)$. Merging two lists ...
5
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 original recurrence.
5
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 proposition and a slightly more rigorous proof. It seems that the proof in the question ignores the requirement that $f$ is defined only on exact powers of $b$.
...
4
Here is one approach. Plug in the definition of $T(n)$ into your first equation, and we get
$$S(n) = 2S(n/4) + S(n/8) + 2T(n/8).$$
Now plug in again and we get
$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4T(n/16).$$
Keep plugging in and eventually we get
$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + 8S(n/64) + \dots + O(1).$$
Now solve that recurrence ...
4
$\log n$ grows slower than $n^\epsilon$ for any $\epsilon>0$. Thus $n\log n$ grows slower than $n^c$ for any $c>1$. However, the third case of the Master theorem requires the existance of a $c>1$ so that $n\log n$ grows at least as fast as $n^c$ (up to a constant factor).
The function is covered by the second case of the Master theorem as given in ...
4
You have to remember that $\sqrt[x]{y} = y^{\frac{1}{x}}$.
Then the rest should follow easily.
Don't look at the following unless you're genuinely stuck.
4
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}}) + \Theta( \lg \lg n)\\
& = T(n^{\frac{1}{4}}) + \Theta(\lg 2^{-1} \lg n) + \Theta( \lg \lg n)\\
& = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n - 1) + \...
4
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).$$
4
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 have $$T(2^m)=2T(2^{m/2})+m.$$
Define $S(m)=T(2^m)$. Hence, we have:
$$S(m)=2S(m/2)+m.$$
Developping the recurrence (or you can apply the Master Theorem for $...
4
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(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\
6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\
6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\
6 \sum_{m=1}^{n+1} m = 6\...
4
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)) < n/2$. This can be done as such:
Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i>0$)
Suppose $n$ is even. Then $\...
4
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 maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n < N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq ...
3
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 add some derivation details:
Note that the original runtime $T(n) = 3 T(n/2) + O(n)$. By mathematical induction we can observe that $T(n) = 3^{\log n} + O(n)$, ...
Only top voted, non community-wiki answers of a minimum length are eligible
