31
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$.
21
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.
16
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}\ ...
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 ...
15
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}^{...
14
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
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 ...
10
The picture should say more than words.
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 ...
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
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)$.
□□□...⧆⧆
...
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)....
8
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\...
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
What $S(m) = T(2^m)$ means is that $S$ and $T$ are two different functions which produce the same result while taking inputs as $m$ and $2^m$ respectively.
Function $S$ can be considered as an operator with two internal steps (otherwise, composition of functions):
$S'$ operator: Input:$m$, Output:$2^m$
$T$ operator(original function): Input:output of ...
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
Everything becomes much simpler if when $n$ is odd we stop the sum at $\lfloor n/2 \rfloor$, and when $k$ is even we discount the term corresponding to $k/2$ by a half. In that case you can write
$$ 2T(k) = \sum_{i=1}^{k-1} \binom{k}{i} T(i) T(k-i) $$
and so, putting $T(0) = 0$, we get that for $k \geq 2$,
$$ 2T(k) = \sum_{i=0}^k \binom{k}{i} T(i) T(k-i). \...
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
By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x)+cos^2(x)=1$.
7
You can read this mathematical article:
A fast algorithm for computing large Fibonacci numbers (Daisuke Takahashi):
PDF .
More simple, I implemented several Fibonacci's algorithms in C++ (without and with GMP) and Python. Complete sources on Bitbucket. From the main page you can also follow links to:
The C++ HTML online documentation.
A little mathematical ...
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 ...
7
$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$
Would yield the following summation (assuming $n$ is a power of 2 and base case is $n=2$):
$$
\begin{align}
T(n) &= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\
& = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \...
7
You should really be asking a third question: what happens if $n$ isn't a perfect square. The answer to this question is that the actual recurrence should have $T(\lfloor \sqrt{n} \rfloor)$ or $T(\lceil \sqrt{n} \rceil)$ instead of $T(\sqrt{n})$, though in the analysis we will only consider inputs which are "recursive" squares.
Regarding your first question,...
6
The complexity in your proof is that you have addition in you logarithm, and you need that complexity to go away. So lets get rid of that 34, by just making $n \ge 34$, so now
$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n}{2} \right) = \log(n).$$
I am not sure why the book chose 68, but really its the same argument. If $n \ge 68$, then $...
Only top voted, non community-wiki answers of a minimum length are eligible