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
92
votes
11answers
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 ...
22
votes
2answers
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 ...
20
votes
1answer
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 ...
18
votes
5answers
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 ...
9
votes
2answers
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 ...
12
votes
5answers
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: ...
11
votes
2answers
19k 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 $...
5
votes
3answers
9k views

Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
4
votes
1answer
676 views

Master Theorem and rounding up to the nearest integer

For the master theorem for recurrences of the form $$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$ what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/...
4
votes
3answers
1k views

Run time of recurrence with five uneven calls

I am trying to figure how to find an upper bound for the running time of a given recurrence relation (without proving the bound) using the Iteration method. The recurrence is: $$T(n)=2T\left(\frac{n}{...
18
votes
1answer
530 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 ...
12
votes
3answers
8k 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. ...
5
votes
2answers
659 views

Problems showing the constraint of master theorem case three holds

Prove or disprove the following statements: $T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right)...
3
votes
4answers
5k views

To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$

I have done the proof until the point when $T(n) \leq cn^{\log7}$. But when it comes to finding the value of constant $c$, I am getting stuck. The given recurrence relation is $T(n) = 7T(n/2) + n^2$....
10
votes
3answers
736 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\...
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$$ ...
6
votes
0answers
205 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) + \...
0
votes
2answers
5k views

Solving recurrences using substitution method

I already have a solution for this problem but it's just not making sense to me. Here is the problem (It's from Introduction to Algorithms by CLRS found in CH.4): Show $T(n) = 2T(\lfloor n/2 \...
2
votes
1answer
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 ...
2
votes
1answer
8k views

How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method

The guess solution to the $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$ is $\Theta(n \log{\log n})$. This is my solution: $$ T(n) \leq 2c\left(\frac{n}{2}\right) \log{\log {\frac{n}{2}}} +...
2
votes
1answer
629 views

Median of Medians Recurrence Relation for 3-grouping

So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like $$ T(n) = T(\...
1
vote
0answers
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 ...
0
votes
3answers
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 ...
0
votes
2answers
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)$...
0
votes
1answer
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 ...
11
votes
1answer
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 ...
6
votes
2answers
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 ...
8
votes
1answer
995 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 \...
3
votes
2answers
1k views

How to solve the recurrence: T(n) = n*T(n-1) + n?

In a an exercise I'm required to analyze the runtime of recursive function: ...
3
votes
1answer
882 views

How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n. $$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
2
votes
1answer
3k views

Time complexity of the fast exponentiation method

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &...
15
votes
3answers
8k 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 ...
8
votes
2answers
995 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 [...
6
votes
2answers
2k 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 \...
5
votes
5answers
21k 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
3answers
968 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
2answers
332 views

Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part?

I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain ...
3
votes
2answers
19k views

Solution to recurrence $T(n) = T(n/2) + n^2$

I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$ Recursion tree - ...
3
votes
1answer
65 views

Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
2
votes
3answers
254 views

Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$. I thought first to make a substitution: $m=\log n$. Then: $$ T(2^m)=T(2^{m \over 2})+10\log m $$ Let $S(m)=T(2^m)$: $$ S(m)=S\big({m ...
2
votes
2answers
787 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
2
votes
2answers
52 views

Showing asymptotic lower bound on log of recurrence

I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows: $T(1) ...
2
votes
1answer
2k views

Solving the recurrence $T(n)=T(n-1)*T(n-2)$

I have been trying to solve the following recurrence: $$T(n)=T(n-1)*T(n-2)$$ The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$. I started by taking the $\log_{2}$ of both sides to ...
1
vote
2answers
810 views

Number of ways to make $n$ cents

How to find a recurrence relation for $F(n)$ the number of ways to make n cents change using only pennies (4 cents), nickels(5cents), and dimes(10cents) and ordering matters. There are three ...
0
votes
1answer
1k views

Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method

How can I use the master's method in order to solve the recurrence formula $T(n)=3T(\frac{n}{3})+\sqrt{n}$ ?
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 ...
6
votes
1answer
494 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 ...
3
votes
1answer
166 views

Master Theorem on oscillating function

Consider a recurrence of the form $T(n) = a T(n/b) + f(n)$ Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating). Suppose, however, that $f(n)$ is ...
3
votes
0answers
129 views

Solve Recurrence Equation Problem [duplicate]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n\,.$$ Any nice solution would be highly appreciated. My solution is to substitute $n=3^m$, ...
2
votes
1answer
202 views

Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...