# Questions tagged [recurrence-relation]

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

67 questions
Filter by
Sorted by
Tagged with
23k 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 ...
9k 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 ...
949 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 ...
21k 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 ...
18k 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 ...
3k 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: ...
19k views

1k views

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$$ ...
205 views

2k views

### Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
8k views

786 views

### Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
115 views

### Solving a recurrence of uneven subproblems without Akra-Bazzi

I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$ I observed it ...
83 views

### Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?

To make my question more concrete, here is an example I am stuck on. I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$...
1k views

### Register Machine code for Fibonacci Numbers

I am not sure whether this is the right place to ask this question. I would like to write a register machine code which when given an input of n in register 1, returns (also in register 1) the nth ...
40k 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 ...
42k 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 ...
995 views