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 ...
- 279k
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}\...
- 23.8k
10
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 ...
- 39.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,523
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 ...
- 4,523
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 ...
- 279k
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,764
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,595
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/...
- 279k
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 ...
- 279k
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 ...
- 279k
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,523
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(\...
- 279k
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 ...
- 279k
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,097
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
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 ...
- 279k
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 ...
- 5,902
6
votes
Accepted
Analyzing time complexity for change making algorithm (Brute force)
First, when computing the $n$-th fibonacci number $F(n)$, the number of branches (leaves) is not $2^n$, but exactly $F(n)$. But you can say it is $O(2^n)$.
As for the coin change problem it is not $O(...
- 9,885
6
votes
Accepted
What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?
The function $f(n,m) = \binom{n+m}{n}$ satisfies the recurrence
$$
f(n,m) = f(n-1,m) + f(n,m-1),
$$
with base cases $f(n,0) = f(0,m) = 1$. This already gives you the solution when $c = 0$, assuming ...
- 279k
6
votes
Accepted
Solving recurrence relations with two variables
The standard technique is to notice that your recurrence is just Pascal's identity, and so
$$
T(n,k) = \binom{n}{k}
$$
is a solution to the recurrence. There are other solutions, for example $T(n,k) = ...
- 279k
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$ ...
- 39.1k
5
votes
Accepted
Recurrence which cannot be analyzed by master theorem
Suppose for simplicity that $n$ is a power of 2. Construct the tree corresponding to the recursion – each vertex is labelled by the current value of $n$, has three children, one of which is a leaf. We ...
- 279k
5
votes
Accepted
A better upper bound to a recursive function
Solving your recurrence, assuming the base case $T(0) = 1$, we get
$$
\begin{align*}
T(n) &= 1 + nT(n-1) \\ &=
1 + n + n(n-1)T(n-2) \\ &=
1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &= \...
- 279k
5
votes
Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
An alternative solution still using domain transformation/change of variables.
$$T(n) = T(\sqrt{n}) + \log \log n$$
1. Let $m = \log n$
We can then define a new function $S$ based on how $m$ ...
- 4,523
5
votes
Accepted
Solving the recurrence $T(n)=T(n−1)/T(n−2)$
Then assume $T(0) = a, T(1)=b$ such as $a \neq 0$ and $b \neq 0$.
You could write down first few terms and deduce the pattern
$$T(0)= a$$
$$T(1)= b$$
$$T(2)= \frac{T(1)}{T(0)} = \frac{b}{a}$$
$$T(3)= \...
- 9,885
5
votes
Accepted
How do I know the height from recursion tree of $T(n)=4T(n/2+2)+n$?
Suppose that $n = 2^m+4$. Then
$$
\frac{n}{2} + 2 = \frac{2^m+4}{2} + 2 = (2^{m-1} + 2) + 2 = 2^{m-1} + 4.
$$
We conclude that if $n = 2^m+4$ then the height is $m$ (or $m+1$, depending on how you ...
- 279k
5
votes
Accepted
How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?
On the one hand, we have
$$
\begin{align*}
T(n) &\geq n^2 + nT(n-1) \\ &\geq n^2 + n(n-1)^2 + n(n-1) T(n-2) \\ &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + n(n-1)(n-2)T(n-3)
\end{align*}
$$
and ...
- 279k
5
votes
Accepted
Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences
Yes. This generalizes to any linear recurrence. Suppose we have the linear recurrence
$$x_{n+1} = a_0 x_n + a_1 x_{n-1} + \dots + a_k x_{n-k}.$$
Define the column vector $v_n = (x_n,x_{n-1},\dots,...
D.W.♦
- 166k
Only top scored, non community-wiki answers of a minimum length are eligible