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$.
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.
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
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
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
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
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.
...
7
Calculus of differences
We make Kaya's nice observations slightly more formal. The sequence $T^k$ is the $k$th difference sequence of the original sequence $T$. You can think of it as a discrete $k$th derivative. For example, if $T$ is a $k$th degree polynomial then $T^k$ is constant. We will see below what happens when $T$ is exponential.
For a sequence $...
7
A simple, specific example of an algorithm with a type $(iii)$ recurrence is binary search. At each point you decide whether to look in the left or the right half of the current section of the array, so your problem halves, and you only have one subproblem. The recurrence is then $T(n) = T(\frac{n}{2}) + O(1)$.
So you might get a type $(iii)$ any time you "...
7
You started with the induction hypothesis $T(k) \le ck/3$ for all $k<n$, but you didn't prove that $T(n)\le cn$. You concluded that $T(n) \le c_1 n$, for a different constant $c_1 \ne c$. For the induction proof to work, you have to use the same constant in the induction hypothesis and the conclusion.
7
Note that $3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$. So the $-\frac 12$ indeed becomes a constant factor that is absorbed by the $O()$, but $\frac n2$ in the exponent changes the base and changing the base changes the $O$-class.
The correct answer thus is $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.
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
Suppose that the rectangle to be tiled has 3 rows and $n$ columns.
□□□...□
□□□...□
□□□...□
123...n
Consider a tiling of this rectangle using 2$\times$1 dominos. There are two basic options:
All tiles touching the $n$th column are horizontal. There must be 3 of them, and if you remove them, you get a tiling of a rectangle of size $3\times(n-2)$.
□□□...⧆⧆
...
7
For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$.
Whenever confronted with a new dynamic programming problem, you should always try to understand how optimal solutions are structured in terms of optimal solutions for smaller subproblems (cf. optimal substructure). This will help ...
Only top voted, non community-wiki answers of a minimum length are eligible
