Questions tagged [recurrence-relation]

a definition of a sequence where later elements are expressed as a function of earlier elements.

Filter by
Sorted by
Tagged with
90
votes
11answers
18k 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 ...
20
votes
2answers
8k 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 ...
20
votes
1answer
746 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 ...
20
votes
1answer
381 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 ...
19
votes
5answers
4k views

How long does the Collatz recursion run?

I have the following Python code. ...
18
votes
5answers
16k 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 ...
18
votes
1answer
521 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 ...
15
votes
3answers
6k 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 ...
11
votes
3answers
2k 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: ...
11
votes
3answers
6k 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. ...
11
votes
2answers
13k 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 $...
10
votes
3answers
651 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\...
10
votes
1answer
1k 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 ...
10
votes
1answer
453 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 ...
9
votes
1answer
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 ...
9
votes
1answer
21k 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 ...
9
votes
1answer
23k 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 ...
8
votes
1answer
503 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) \...
8
votes
2answers
296 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, ...
8
votes
2answers
843 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 [...
8
votes
1answer
119 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 ...
8
votes
2answers
242 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, ...
8
votes
1answer
342 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: ...
7
votes
3answers
6k 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)...
7
votes
2answers
9k 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 ...
7
votes
1answer
10k 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 ...
7
votes
2answers
517 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\...
7
votes
1answer
2k 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 ...
7
votes
1answer
878 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 \...
7
votes
2answers
2k 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$$ ...
7
votes
1answer
113 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 $\...
6
votes
2answers
32k 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 ...
6
votes
2answers
1k 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 \...
6
votes
4answers
773 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 ...
6
votes
1answer
123 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 ...
6
votes
1answer
752 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 ...
6
votes
1answer
282 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
1answer
687 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 ...
6
votes
1answer
800 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 ...
6
votes
1answer
2k 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-...
6
votes
1answer
175 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: ...
6
votes
1answer
85 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 ...
6
votes
1answer
424 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 ...
6
votes
0answers
203 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) + \...
5
votes
5answers
15k views

How do I show T(n) = 2T(n-1) + k is O(2^n)?

This is a practice problem I've come up with in order to study for an exam I have in a couple of hours. Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant. ...
5
votes
1answer
380 views

How to solve a recurrence relation with a sum?

How do I solve the following recurrence relation? $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j). $$ I thought of solving it by generating its recursion tree. I found that the height of the tree would be ...
5
votes
3answers
1k views
5
votes
3answers
605 views

Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm?

The book I am following explains the solution as, As we can see,the size of sub problems at the first level of recursion is $n$.So, let us guess that $T(n)=O(n\log n)$ and try to prove that our ...
5
votes
3answers
9k views

Solving $T(n)=4T(n/2)+n^2$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T(n/2)+n^2$$ My guess is $T(n)$ is $\Theta(n\log n)$ (and I am sure about it because of master ...
5
votes
2answers
1k views

Why does the recurrence equation for QuickSort consider all the elements in the array?

I have been taught that QuickSort has the following recurrence equation in the best case: $T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \...

1
2 3 4 5
11