12
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 ...
11
If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold:
$f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$
Our recurrence is defined as ...
10
Not a rigorous proof, but a "from the top of my head" explanation.
Imagine the recurrence $aT(n/b)+f(n)$ as a tree. The third case covers the scenario when the root node dominates the running time asymptotically, i.e. most of the work is being done in measly node on top of the recurrence tree. Then the running time is $\Theta(f(n))$.
To make sure the root ...
9
We will use Raphael's suggestion and unfold the recurrence. In the following, all logarithms are base 2. We get
$$
\begin{align*}
T(n) &= n^{1/2} T(n^{1/2}) + cn \\
&= n^{3/4} T(n^{1/4}) + n^{1/2} c n^{1/2} + cn\\
&= n^{7/8} T(n^{1/8}) + n^{3/4} c n^{1/4} + 2cn\\
&= n^{15/16} T(n^{1/16}) + n^{7/8} c n^{1/8} + 3cn \\
& \ldots \\
&= \...
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
Let $a = 1$ and $b = 2$, so that
$$ T(2^n) = \sum_{k=0}^n f(2^k). $$
For case 3 to apply, we need $f(n) = \Omega(n^\epsilon)$ (for some $\epsilon > 0$) and the regularity condition, $f(n/2) \leq (1-\delta) f(n)$ (for some $\delta > 0$). You get the regularity condition from the proof, i.e. it's a proof-generated concept. While the regularity condition ...
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)\...
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
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
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
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
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
Yes, $ n\log n = \Omega(n) $ is true.
To see why, note that for this to be true, we have to show that $ n\log n \ge cn$ for all $n \gt n_0 $ and $ \exists c \gt 1 $. If we take $ c = 1 $ then, we get $n\log n \ge n$ for all $n \ge 2$. This shows that $ n\log n = \Omega(n) $ is true.
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
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
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
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$...
5
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 ...
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
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.
4
The following shows that the second statement is false.
Define $f$ as follows:
$$ f(n) = \begin{cases} 4n^3 & n \text{ is a power of }4, \\ n^2 & \text{otherwise}. \end{cases} $$
Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while
$$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$
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
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\...
Only top voted, non community-wiki answers of a minimum length are eligible
