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 ...
user avatar
  • 9,325
22 votes
Accepted

Efficient algorithm to compute the $n$th Fibonacci number

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 ...
user avatar
16 votes

Solving a recurrence relation with √n as parameter

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,...
user avatar
  • 14.6k
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 ...
user avatar
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 ...
user avatar
  • 70.9k
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 $$ ...
user avatar
  • 14.6k
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 ...
user avatar
  • 4,747
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}\...
user avatar
  • 18.9k
12 votes

Solving or approximating recurrence relations for sequences of numbers

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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 27.6k
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{...
user avatar
  • 4,371
9 votes
Accepted

Solving recurrence relation with two recursive calls

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$....
user avatar
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 ...
user avatar
  • 34.1k
8 votes
Accepted

Understanding an algorithm for the gas station problem

The problem is in the condition for the first argument to min() in Equation (4) on p. 7. It's currently ...
user avatar
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 ...
user avatar
  • 4,371
8 votes
Accepted

What is the Big O of T(n)?

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)$ ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,336
7 votes
Accepted

Solving the recurrence T(n) = 3T(n-2) with iterative method

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 ...
user avatar
  • 6,519
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 ...
user avatar
7 votes

Changing variables in recurrence relations

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 ...
user avatar
7 votes
Accepted

Solution of complex recurrence relation

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 $$ ...
user avatar
7 votes
Accepted

Master Method to solve recurrences is 'a' related to 'b'?

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 ...
user avatar
7 votes
Accepted

What is the correct representation of Master Theorem?

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)+...
user avatar
  • 1,944
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 ...
user avatar
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 \...
user avatar
  • 4,371
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(\...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible