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 ...
20
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.
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 ...
16
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
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
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
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
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
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
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}\ ...
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
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
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
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
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 ...
9
The picture should say more than words.
8
After checking this post again, I'm surprised this isn't on here yet.
Domain Transformation / Change of Variables
When dealing with recurrences it's sometimes useful to be able to change your domain if it's unclear how deep the recursion stack will go.
For instance, take the following recurrence:
$$T(n) = T(2^{2^{\sqrt{\log \log n}}}) + \log \log \log n$...
8
The problem is in the condition for the first argument to min() in Equation (4) on p. 7. It's currently
c(v) <= c(u) and g < d[u][v]
but it should be
(c(v) <= c(u) or v = t) and g < d[u][v]
to force arrival at t to have no gas left. (Just as with my explanation below for the bug in Fill-Row(u, q), we are never interested in the cost of gas ...
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 ...
8
Assuming an appropriate base case, it is easy to see that $T(n) \geq (n/\log_2 n) \cdot x$, since at each step we subtract at most $\log_2 n$, and thus it takes t least $n/\log_2 n$ steps to reach zero.
In the other direction, denote by $m$ the current input ($n$, $n-\log_2n$, and so on). As long as $m \geq n/2$, the input decreases by at least $(\log_2 n)/...
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
Case 2 of the master theorem, as usually stated, handles only recurrences of the form $T(n) = aT(n/b) + f(n)$ in which $f(n) = \Theta(n^{\log_ab}\log^k n)$ for $k \geq 0$. The following theorem, taken from a handout of Jeffrey Leon, gives the answer for negative $k$:
Consider the recurrence $T(n) = a T(n/b) + f(n)$ with an appropriate base case.
...
Only top voted, non community-wiki answers of a minimum length are eligible
