# Questions tagged [recurrence-relation]

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

516 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
4k views

### How long does the Collatz recursion run?

I have the following Python code. ...
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 ...
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 ...
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 ...
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: ...
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. ...
13k views

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 ...
878 views

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 ...