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 ...
Evil's user avatar
  • 9,425
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 ...
Yuval Filmus's 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 ...
Raphael's user avatar
  • 72k
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 ...
Sarvottamananda's user avatar
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}\...
Pseudonym's user avatar
  • 21.6k
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 ...
user340082710's user avatar
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{...
ryan's user avatar
  • 4,431
9 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 ...
ryan's user avatar
  • 4,431
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 ...
John L.'s user avatar
  • 38.6k
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 ...
Yuval Filmus's 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 ...
Mario Cervera's 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 ...
Jakube's user avatar
  • 1,585
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/...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's 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 \...
ryan's user avatar
  • 4,431
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(\...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Tom van der Zanden's user avatar
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 ...
Lee's user avatar
  • 1,077
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 "...
Christopher's user avatar
6 votes

How to solve T(n) = T(n-1) + n^2?

Just start with: $\begin{align} T(k) - T(k - 1) &= k^2 \\ \sum_{1 \le k \le n} (T(k) - T(k - 1)) &= \sum_{1 \le k \le n} k^2 \\ T(n) - T(0) &= \frac{n (n + 1) (2 n + 1)}{...
vonbrand's user avatar
  • 13.9k
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}$, ...
HEKTO's user avatar
  • 3,048
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 ...
Yuval Filmus's user avatar
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.'s user avatar
  • 156k
6 votes

Applying the Master Theorem on Merge sort

You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you ...
Yuval Filmus's user avatar
6 votes

Algorithms - Solving recurrence-relations/Bounds?

First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence. Second, your recurrence only possibly makes ...
Yuval Filmus's user avatar
6 votes
Accepted

Error solving the next recurrence: $T(n)=7T(n/2)+n^2$

Some of your sums have typos, but you already have the right answer. Here's a useful fact about logarithms: $a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$ Apply it ...
Craig Gidney's user avatar
  • 5,802
6 votes
Accepted

The recursion $T(n) = T(n/2)+T(n/3)+n$

If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction. $$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$ More generally, let $c\gt6$ be a constant such that $T(1)\le c$ ...
John L.'s user avatar
  • 38.6k

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