Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
741
questions
98
votes
11
answers
29k
views
Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...
- 72.8k
23
votes
2
answers
11k
views
Changing variables in recurrence relations
Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations.
The following method can be illustrated with this ...
- 331
20
votes
1
answer
1k
views
Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
- 72.8k
20
votes
1
answer
410
views
Solving divide & conquer reccurences if the split-ratio depends on $n$
Is there a general method to solve the recurrence of the form:
$T(n) = T(n-n^c) + T(n^c) + f(n)$
for $c < 1$, or more generally
$T(n) = T(n-g(n)) + T(r(n)) + f(n)$
where $g(n),r(n)$ are some ...
- 433
19
votes
1
answer
563
views
Proving the (in)tractability of this Nth prime recurrence
As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
- 549
18
votes
5
answers
7k
views
18
votes
5
answers
23k
views
Solving a recurrence relation with √n as parameter
Consider the recurrence
$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$
for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.
I know the Master theorem for ...
- 283
16
votes
3
answers
13k
views
Solving Recurrence Equations containing two Recursion Calls
I am trying to find a $\Theta$ bound for the following recurrence equation:
$$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$
I figure Master Theorem is inappropriate due to differing amount of ...
- 544
16
votes
5
answers
4k
views
Efficient algorithm to compute the $n$th Fibonacci number
The $n$th Fibonacci number can be computed in linear time using the following recurrence:
...
- 271
12
votes
3
answers
10k
views
Understanding an algorithm for the gas station problem
In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. ...
- 223
12
votes
2
answers
21k
views
Master theorem not applicable?
Given the following recursive equation
$$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that
$$ n^{\log_2(2)} = n.$$
Now we check the first two cases for $...
- 223
12
votes
1
answer
65k
views
Solving T(n) = 2T(n/2) + log n with the recurrence tree method
I was solving recurrence relations. The first recurrence relation was
$T(n)=2T(n/2)+n$
The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree ...
- 1,717
11
votes
1
answer
2k
views
Intuition behind the Master Theorem
The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following:
For a recurrence ...
- 1,158
10
votes
3
answers
794
views
Error in the use of asymptotic notation
I'm trying to understand what is wrong with the following proof of the following recurrence
$$
T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n
$$
$$
T(n) \leq 2\left(c\left\...
- 373
10
votes
1
answer
2k
views
Solving recurrence relation with two recursive calls
I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very.
In order to do this I ask myself the question ...
- 13.8k
10
votes
1
answer
555
views
Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply)
Suppose an algorithm has a runtime recurrence relation:
$ T(n) = \left\{
\begin{array}{lr}
g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\
f(n) & : n < n_0
...
- 669
9
votes
1
answer
1k
views
Solving Recurrences via Characteristic Polynomial with Imaginary Roots
In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials.
Say I have concluded that ...
- 221
9
votes
2
answers
32k
views
Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence
$$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$
by applying the Master Theorem.
I am ...
- 461
9
votes
2
answers
1k
views
Why does Akra-Bazzi need that toll-function g is bounded?
Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper [...
- 72.8k
9
votes
1
answer
1k
views
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.
The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing
$\qquad \...
- 919
9
votes
1
answer
6k
views
Analyzing time complexity for change making algorithm (Brute force)
I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so:
Since the tree can have a maximum height of 'n' and at every ...
- 193
9
votes
1
answer
30k
views
Recurrence for recursive insertion sort
I tried this problem from CLRS (Page 39, 2.3-4)
We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively ...
- 277
9
votes
1
answer
546
views
What is the running time of this recursive algorithm?
I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037.
This is my proposed solution to compute the $n$th value:
...
- 205
8
votes
3
answers
17k
views
Recurrence relation for time complexity $T(n) = T(n-1) + n^2$
I'm looking for a $\Theta$ approximation of
$$T(n) = T(n-1) + cn^{2}$$
This is what I have so far:
$$
\begin{align*}
T(n-1)& = T(n-2) + c(n-1)^2\\
T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex]
T(n-2)...
- 215
8
votes
1
answer
539
views
Big-O proof for a recurrence relation?
This question is fairly specific in the manner of steps taken to solve the problem.
Given
$T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$.
So the steps were as follows. We want to prove that $T(n) \...
- 113
8
votes
2
answers
727
views
Reccurence $T(n) = \sqrt{n}T(\sqrt{n})+n$
Note: this is from JeffE's Algorithms notes on Recurrences, page 5.
(1). So we define the recurrence $T(n) = \sqrt{n}T(\sqrt{n})+n$ without any base case. Now I understand that for most recurrences, ...
- 83
8
votes
1
answer
160
views
Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$
I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input.
The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$.
It ...
- 81
8
votes
2
answers
298
views
Maximum number of points that two paths can reach
Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, ...
- 1,131
7
votes
3
answers
10k
views
Solving the recurrence T(n) = 3T(n-2) with iterative method
It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given:
$$T(n) = 3T(n-2)$$
My first step was to iteratively ...
- 213
7
votes
1
answer
148
views
Solving or estimating the recurrence $T(n) = x + T(n-\log_2 n)$
I am trying to either solve or find a tight bound $\Theta$ for the following recurrence relation:
$$T(n) = x + T(n-\log_2 n)\,.$$
For some nonzero constant $x$ (we can suppose it to be 1, for ...
- 73
7
votes
1
answer
3k
views
What is the Big O of T(n)?
I have a homework that I should find the formula and the order of $T(n)$ given by
$$T(1) = 1 \qquad\qquad
T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.
$$
I've established that $T(n) = \frac{1}{n}$ but now ...
- 478
7
votes
2
answers
3k
views
Solving Recurrence Relations 'Chip & Conquer'
I've been tasked with solving some recurrence relations, and I've been running into trouble with so called 'chip & conquer' relations.
Here are some example problems:
$$T(n) = T(n-5) + cn^2$$
...
user906153
7
votes
1
answer
163
views
Trouble understanding the master theorem, from Jeffrey Erickson's Notes
I'm looking at Jeffrey Erickson's Notes on the master theorem
(page 10).
Part (b) of the theorem states that if $T(n) = aT(\frac{n}{b})+f(n)$, $af(\frac{n}{b}) = kf(n)$ and $k>1$ then T(n) is $\...
- 204
6
votes
2
answers
57k
views
How to solve T(n) = T(n-1) + n^2?
See title. I'm trying to apply the method from this question. What I have so far is this, but I don't know how to proceed from here on:
T(n) = T(n-1) + n2
T(n-1) = T(n-2) + (n-1)2 = T(n-2) + n2 - 2n ...
- 195
6
votes
2
answers
4k
views
Relation between the size of sub-problems and number of sub-problems in a recurrence
Below is a well-known equation for generalized recurrence relation in a divide and conquer paradigm (as described in CLRS) --
$$T(n) = aT(n/b) + f(n), \quad \text{where} \quad a \gt 1 \text{ , } b \...
- 541
6
votes
2
answers
3k
views
The recursion $T(n) = T(n/2)+T(n/3)+n$
I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).
Using induction, I found that $T(n) = O(n\...
- 163
6
votes
4
answers
1k
views
What is the number of expressions containing n pairs of matching brackets with nesting limit?
I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching ...
- 1,131
6
votes
2
answers
20k
views
Finding the height of a d-ary heap
I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following:
The parent of a node $i$ is given by: $\left\lfloor\frac{i+1}{d}\right\...
- 517
6
votes
1
answer
919
views
Master theorem and constants independent of $n$
I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version):
$$T(n)=4T(n/2)+O(r)$$
$r$ is independent of $n$. Case 1 of the Master theorem applies ...
- 9,126
6
votes
1
answer
2k
views
Applying the Master Theorem on Merge sort
I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into ...
- 61
6
votes
1
answer
341
views
what is the complexity of recurrence relation?
what is the complexity of below relation
$ T(n) = 2*T(\sqrt n) + \log n$
and $T(2) = 1$
Is it $\Theta (\log n * \log \log n)$ ?
6
votes
1
answer
1k
views
An Alternative Hanoi Tower problem
We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...).
Now we want to move all $2n$ disks to tower $T_3$.
If $T(p,q)$ is a recurrence relation of minimum ...
- 141
6
votes
1
answer
3k
views
Subtracting lower-order term to prove subtitution method works
Substation method fails to prove that $T(n)=\Theta(n^2) $ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$.
I don't understand how to subtract off lower-...
- 461
6
votes
1
answer
178
views
Finding lambda of Master Theorem
Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$.
That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: ...
- 105
6
votes
1
answer
479
views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
- 227
6
votes
1
answer
92
views
Why is $\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]=2^n$?
In CLRS book, in the road cutting example there is a recursion formula
$$
1+\sum_{j=0}^{n-1}T(j)
$$
and it can be proved that the sum is
$$
2^n
$$
by simple induction. In 3-rd ...
- 163
6
votes
1
answer
546
views
Do different variants of Mergesort have different runtime?
One of my courses introduced the following question:
Given the recurrence relation for mergesort:
$T(n) = 2T(n/2) + n$
How would the following parameter passing strategies influence the relation and ...
- 175
6
votes
1
answer
2k
views
Cases of Master Theorem
Suppose that we have $ \\ T(n)=\left\{\begin{matrix}
c, & \ \text{if } n<d\\
aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d
\end{matrix}\right.$
The Master theorem is the ...
- 431
6
votes
1
answer
10k
views
How many comparisons do we need to find min and max of n numbers?
Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers.
Recurrence for the above problem ...
- 749
6
votes
0
answers
220
views
Are there master theorems that deal with parameters of the form $n-c$?
While thinking about this question on a recurrence I checked out some stronger master theorems.
Unfortunately, they do not seem to apply because terms
$\qquad\displaystyle T(n) = \dots + T(n-1) + \...
- 72.8k