31
votes
Accepted
How long does the Collatz recursion run?
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 ...
- 9,385
16
votes
Accepted
How to solve a recurrence relation with a sum?
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 ...
- 274k
15
votes
How long does the Collatz recursion run?
You translated the code correctly. There are many methods for solving recurrences.
However, it is currently unknown if collatz even halts for all ...
- 71.7k
14
votes
Accepted
How to solve T(n) = T(n-1) + n^2?
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
$$
...
- 14.7k
13
votes
How long does the Collatz recursion run?
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 ...
- 4,787
13
votes
Can we solve a "very" exponential recurrence?
It depends what you mean by "solve". This is tetration, and it has a number of "closed" forms. For example:
$$\begin{eqnarray*}T_0 & = & 1 \\ T_{n+1} & = & 2^{T_n}\...
- 20.2k
13
votes
Does T(n) = 2 · T(2n) + n apply to Master method?
The Master Theorem is not deemed to be used with $b<1$. But you can recast the recurrence as
$$T(2n)=\frac12T(n)-\frac n2$$
or
$$T(n)=\frac12T\left(\frac n2\right)-\frac n4.$$
So yes, the Master ...
- 8,797
12
votes
Accepted
Big-O proof for a recurrence relation?
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 ...
- 1,103
10
votes
Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?
The picture should say more than words.
- 29.1k
9
votes
Solving or approximating recurrence relations for sequences of numbers
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{...
- 4,391
9
votes
How to solve T(n)=2T(√n)+log n with the master theorem?
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 ...
- 38.2k
8
votes
Accepted
Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?
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. ...
- 274k
8
votes
Solving or approximating recurrence relations for sequences of numbers
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 ...
- 4,391
8
votes
Accepted
Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$
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 ...
- 274k
8
votes
Accepted
Recurrence relation of the coin change problem
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 ...
- 3,604
8
votes
Accepted
Solving recurrence relation with square root
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 ...
- 1,570
8
votes
Accepted
Intuition behind the Master Theorem
You can use repeated substitution to obtain
$$
T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots
$$
Now suppose that $f(n) = n^\gamma$. Then
$$
\begin{align*}
T(n) &= n^\gamma + a (n/b)^\gamma + a^2 (n/...
- 274k
8
votes
How to solve $T(n)= 4T(\sqrt n) +\log^2n$?
Let $S(n) = T(2^n)$. Then
$$
S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.
$$
You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the ...
- 274k
7
votes
Efficient algorithm to compute the $n$th Fibonacci number
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 ...
- 173
7
votes
Solving or approximating recurrence relations for sequences of numbers
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 ...
- 274k
7
votes
Accepted
How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method
$$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 \...
- 4,391
7
votes
Accepted
Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$
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(\...
- 274k
7
votes
Accepted
Master theorem for $T(n)=T(n-1)+O(n)$
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 ...
- 274k
6
votes
Solving divide & conquer reccurences if the split-ratio depends on $n$
Let's say you have a recurrence
$$
T(n) = \begin{cases}
T(n - n^c) + T(n^c) + f(n) & \text{n > 2} \\
1 & \text{otherwise}
\end{cases}
$$
that ranges over positive reals.
What can we do ...
- 1,057
6
votes
Recurrence relations that do not have a closed form solution
Yes, there are. Consider the recurrence $a_{n+1}=(7a_n/4 + 1/2) - (5a_n/4 + 1/2)(-1)^{a_n}$ where $a_0$ is a given integer value. It is well known that this gives the Collatz sequence. There is no "...
- 61
6
votes
Accepted
Recurrence Relation(with Square root)
Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $...
- 13.3k
6
votes
Accepted
Using the Master theorem on a recurrence with non-constant a
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 ...
- 13.1k
6
votes
Solving T(n) = 2T(n/2) + log n with the recurrence tree method
The non-recursive term of the recurrence relation is the work to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, ...
- 3,060
6
votes
Accepted
Time complexity of the fast exponentiation method
Instead of time complexity, it is much simpler here to count multiplications; I'll leave you to figure out the relation between multiplications and time complexity (the exact relation depends on the ...
- 274k
6
votes
Accepted
Master Theorem and rounding up to the nearest integer
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-...
D.W.♦
- 152k
Only top scored, non community-wiki answers of a minimum length are eligible