15
Yes, recursion trees do still work! It doesn't matter at all whether the base case occurs at $T(0)$ or $T(1)$ or $T(2)$ or even $T(10^{100})$. It also doesn't matter what the actual value of the base case is; whatever that value is, it's a constant.
Seen through big-Theta glasses, the recurrence is $T(n) = 2T(n/2)+T(n/3)+n^2$.
The root of the recursion ...
14
You can use the more general Akra-Bazzi method.
In your case, we would need to find $p$ such that
$$ \frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$$
(which gives $p \approx 1.364$)
and we then have
$$T(x) = \Theta(x^p + x^p\int_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$$
Note that you don't really need to solve for $p$. All you need to know is that $1 \lt p \...
10
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 ...
10
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 ...
10
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}\ ...
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 \\
&= \...
7
The three cases of the Master Theorem that you refer to are proved in the Introduction to Algorithms by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest and Clifford Stein (2nd Edition, 2001).
It is correctly observed that the recurrence in question falls between Case 2 and Case 3. That is $f(n) = n \log n$ grows faster than $n$ but slower than $n^{1+\...
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
Use a recursion tree (otherwise known as the proof of the Master Theorem). I'll assume here that $r>1$, since otherwise the recurrence never bottoms out.
The root of the recursion tree for $T(n)$ has value $nr^2$.
The root has $r^2$ children, each with value $(n/r)r^2 = nr$. Thus, the total value of all children is $nr^3$.
Each child has $r^2$ children ...
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 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)....
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
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
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
$f(n) = (n\cdot \lg n)^{1/2}$ and $n^{\log_b a}=n^{2/3}$, thus
$f(n) = O(n^{\log_b a})$ and even $f(n) = O(n^{\log_b a - \epsilon})$ for $\epsilon < 1/6$.
Why? because
$$\lim_{n\to\infty} \frac{f(n)}{n^{\log_b a - \epsilon}} = \lim_{n\to\infty}\frac{n^{1/2}\lg^{1/2}n}{n^{2/3-\epsilon}} = \lim_{n\to\infty} \frac{\lg^{1/2}n}{n^{1/6-\epsilon}} =0 \quad\...
5
As you correctly noted, the case 1 of the Master theorem applies here. In other words, the case 1 applies if $f(n) = O(n^{\log_b a - \lambda})$ for some constant $\lambda > 0$.
Indeed, we will have to see if we can find some $\lambda > 0$ so that in this case, $\log n = O(n^{\log_4 2 - \lambda}) = O(n^{1/2-\lambda})$. Easy, we can pick any $\lambda &...
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
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$...
4
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.
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
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.
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
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*}
\...
Only top voted, non community-wiki answers of a minimum length are eligible
