34
Converting Full History to Limited History
This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...
29
This is Collatz conjecture - still open problem.
Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence relation, moreover it may not halt at all - so until proven, the running time is unknown and may be $\infty$.
27
Generating Functions $\newcommand{\nats}{\mathbb{N}}$
Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.
This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...
20
Master Theorem
The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is ...
17
Guess & Prove
Or how I like to call it, the "$\dots$ technique". It can be applied to all kinds of identities. The idea is simple:
Guess the solution and prove its correctness.
This is a popular method, arguably because it usually requires some creativity and/or experience (good for showing off) but few mechanics (looks elegant). The art here is to ...
15
The Akra-Bazzi method
The Akra-Bazzi method gives asymptotics for recurrences of the form:
$$
T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for $x \ge x_0$}
$$
This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h_i(x)$ can cater for divisions that don't come out ...
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 ...
15
It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.
This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. ...
15
You translated the code correctly. There are many methods for solving recurrences.
However, it is currently unknown if collatz even halts for all n; the claim that it does is known as Collatz conjecture. Therefore, no known method will work on this recurrence.
I think $T(n)$ will be $\lg n$ if $n$ is even
How so? I guess you are thinking of $n=2^k$, for ...
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 \...
14
Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form
$$ T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n, $$
for some $A,B$. Note that $|(1-\sqrt{5})/2| < 1$, and so the second term tends to zero as $n \longrightarrow \infty$. ...
14
You can use matrix powering and the identity
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.
$$
In your model of computation this is an $O(\log n)$ algorithm if you use repeated squaring to implement the powering.
14
Here are several ways to solve your recurrence relation.
Guessing
Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m < n$ then
$$
T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{...
13
Don't expand the squared terms; it'll just add confusion. Think of the recurrence as
$$
T(\fbox{foo}) = T(\fbox{foo}-1)+\fbox{foo}\;^2
$$
where you can replace foo with anything you like. Then from
$$
T(n)=T(n-1)+n^2
$$
you can replace $T(n-1)$ by $T(n-2)+(n-1)^2$ by putting $n-1$ in the boxes above, yielding
$$
T(n) = [T(n-2) + (n-1)^2]+n^2 = T(n-2)+(n-1)^2+...
13
The time complexity function is
\begin{cases}
T(n)= O(1) \text{ for } n\le 1\\
T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\
T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\
\end{cases}
which can be rewritten as the following if you are interested in asymptotic time complexity.
\begin{cases}
T(n)= 1 \text{ for } n\le 1\\
T(n)=T(n/2) + 1 \text{ for } n\...
12
Let's say the final goal is to prove $T(n) = \mathcal{O}(n)$. You start with the induction hypothesis:
$T(i) \leq ci$ for all $i < n$.
And to complete the proof, you have to show that $T(n) \leq cn$ as well.
However, what you're able to deduce is $T(n) \leq (c+1)n$, which is not helpful to complete the proof; you need one constant $c$ for (almost) all ...
12
Yes, the solution is in fact $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$ determined by the base cases. If the bases cases are real, then (by induction) all the complex terms in $T(n)$ will cancel, for all integer $n$.
For example, consider the recurrence $T(n) = 2T(n-1) - 2T(n-2)$, with base cases $T(0)=0$ and $T(1)=2$. ...
12
Summations
Often one encounters a recurrence of the form
$$ T(n) = T(n-1) + f(n), $$
where $f(n)$ is monotone. In this case, we can expand
$$ T(n) = T(c) + \sum_{m=c+1}^n f(m), $$
and so given a starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$.
Non-decreasing $f(n)$
When $f(n)$ is monotone non-...
12
As you pointed out, the reason for splitting the term into two pieces is to be able to cancel the $an$ term. If we go directly from $(8/9)cn^2 + an \leq cn^2 + an$, then we get stuck as we cannot do anything with the $an$ term. By splitting it in the way described, this allows the $(1/9)cn^2$ to be larger than $an$ when $c \geq 9a$, which then gives you the ...
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 ...
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 ...
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
There may be times when you come across a strange recurrence like this:
$$T(n) = \begin{cases}
c & n < 7\\
2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7
\end{cases}$$
If you're like me, you'll realize you can't use the Master Theorem and then you may think, "hmmm... maybe a recurrence tree analysis could work." Then ...
9
Sedgewick and Flajolet have done extensive work in analytic combinatorics, which allows recurrences to be solved asymptotically using a combination of generating functions and complex analysis. Their work allows many recurrences to be solved automatically, and has been implemented in some computer algebra systems.
This textbook on the subject was written ...
9
Just continue your reasoning as follows.
\begin{eqnarray}
T(n) &=& T(n-1) + cn^2 \\
&=& T(n-2) + c(n-1)^2 + cn^2 \\
&=& \ldots \\
&=& T(n-n) + c(1^2) + c(2^2) + \ldots cn^2 \\
&=& T(0) +c\sum_{1\leq i\leq n} i^2.
\end{eqnarray}
Do you know how to simplify this using the addition formula for the first $n$ squares?
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 \\
&= \...
9
As you mention, the Akra–Bazzi theorem shows that the solution to the recurrence $T(n,p)$ is $O(n\log n)$ for all $p \in (0,1)$. However, this does not reveal the nature of the dependence on $p$. To determine the latter, we can use a recursion tree approach.
At the root of the recursion tree is the interval $\{1,\ldots n\}$. Its two children are the ...
8
You've omitted a few steps. It looks like you're attempting to prove by induction that $T(n) = O(n)$, and your proof goes:
Suppose $T(k) = O(k)$ for $k<n$. This means $T(k) \le c \, k$ for some $c$. Then $T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$, so $T(n) = O(n)$.
This proof goes wrong right from the start: “$T(k)...
answered Mar 26 '12 at 1:26
Gilles 'SO- stop being evil'
38.2k7 gold badges102 silver badges166 bronze badges
8
Yes, all functions $f(n)$ satisfy $f(n) \in O(f(n))$. The definitions are meaningful even if $f(n)$ isn't the running time of any function. Indeed, this notation comes from number theory, where $f(n)$ is usually some error term. Even in computer science, sometimes big O notations is used while analyzing algorithms for something other than a running time or ...
Only top voted, non community-wiki answers of a minimum length are eligible
