# Tag Info

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,325
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 ...
• 270k

### 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,...
• 14.6k
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 ...
• 270k

### 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 ...
• 70.9k
Accepted

• 18.9k

### 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 ...
• 270k
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

### Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

The picture should say more than words.
• 27.6k

• 270k
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 ...
• 1,103