Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recurrence-relation]

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

1
vote
1answer
26 views

Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method: $$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$ First, we have: $a = 10,\ b = 2$ ...
1
vote
1answer
37 views

Solve the recurrence relation T(n)=3T(√n)+lg(n) [duplicate]

Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem. So, how I will find Θ of T(n)?
2
votes
2answers
44 views

Recurrence relation of quicksort depending on its pivot

I understand how the recurrence relation of quicksort is $T(n) = 2T(n/2)+\mathcal{O}(n)$, but if we are guaranteed a certain pivot, for example $n/4$th smallest element to be the pivot every time, ...
2
votes
1answer
29 views

Maximum Expected Fishing Day (Recurrence Relation)

John joined a meetup where organize day long fishing trip once a month. The organizers are vary poor at planning, so will organize fishing on a random day of the month without any advance notice. ...
1
vote
1answer
20 views

Using master theorem to solve recurrence with log [duplicate]

I'm not sure how to solve apply the master theorem in order to solve this recurrence: $$ T(n) = 4T(n/3) +O(n\log n),\text{ where } T(1) = 1.$$ The master theorem I have been shown is normally ...
0
votes
1answer
24 views

Find the computational complexity of the given program

int seq(int n) { if(n == 0 || n == 1) return n; return(seq(floor(n/2)) + seq(ceil(n/2)); } Find the computational complexity of the above program. ...
1
vote
1answer
32 views

Computing number of ways to make change

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total ...
1
vote
1answer
33 views

How to write recurrence relation for backtracking problem?

I am not able to understand how to write a recurrence relation for n queen problem. I searched on web and everywhere it was given directly without explaining how can we arrive to that. Recurrence ...
0
votes
0answers
30 views

How do I show that an iterative solution to Tower of Hanoi performs the same exact steps as a recursive solution? [duplicate]

So given the typical recursive solution to the Tower of Hanoi problem wherein you reduce the n-disk tower to two instances of an (n-1)-disk tower i.e move (n-1) disks from start to auxiliary. move ...
2
votes
1answer
62 views

Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows....
2
votes
2answers
69 views

Solving $T(n) = 3T(n-1) + 2$

I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence: $$T(n) = 3T(n-1) + 2, \quad\quad T(1) = ...
0
votes
0answers
10 views

forming recurrence equations from code [closed]

Please could someone help me with understanding how to form recurrence equations when reading code? I'm having some trouble in my class: ...
3
votes
1answer
38 views

Solving recurrence relations with two variables

I am trying to solve this recurrence relation with two variables: $$T(n, k) = T(n - 1, k - 1) + T(n - 1, k)$$ The base cases are: $T(n, k) = 1$ if $k = 0$ $T(n, k) = 0$ if $k > n$ I was ...
2
votes
3answers
55 views

Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1 [duplicate]

Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and $T(1)=1$. My attempt: I tried back substituting but I am unable to find a general pattern: $$\begin{align*} T(n) &=2^2 T(n-2)...
1
vote
1answer
34 views

Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ ...
1
vote
0answers
23 views

Recurrence Relation for Column Major Form of multidimensional array

A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[...
2
votes
1answer
46 views

Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$

Given positive constants: $c_1, c_2, ..., c_k, c^\prime$, assume that $T(n) = T(c_1n) + T(c_2n) + ...+ T(c_kn) + c^\prime n$ There are two cases: $c_1 + c_2 + ...+ c_k < 1$ $c_1 + c_2 + ...+ c_k ...
1
vote
1answer
72 views

How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?

Like in the title the following equation: F(n)=F(n-1)+F(n-2)+f(n) F(0)=0, F(1)=1 ...
0
votes
1answer
38 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
1
vote
0answers
30 views

Trouble with Master Theorem concerning logarithm and square root [duplicate]

I have trouble understanding how to apply the master theorem in the following problem: $$T_2(1) = 1; T_2(n) = 4T_2(2^{\log \lfloor \frac{n}{2}\rfloor}) + \sqrt{n} \text{ for } n > 1.$$ My ...
0
votes
2answers
56 views

How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$?

The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.
1
vote
1answer
65 views

What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?

Consider the recurrence $$ T(n,m) = T(n,m-1) + T(n-1,m) + c, $$ with base cases $T(n,0) = T(0,m) = 1$. This is the complexity of a recursive algorithm for the longest common subsequence, I know that ...
1
vote
2answers
77 views

How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?

$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$. I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess ...
2
votes
2answers
42 views

Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$ But is it possible to use the master theorem for recurrence relations of the form $T(n) = ...
-2
votes
1answer
127 views

How to solve $T(n) = 3 T(n-1) + 10 T(n-2) + 7 \cdot 5 ^ n$?

Consider the recurrence $$ T(n) = 3 T(n-1) + 10 T(n-2) + 7 \cdot 5 ^ n, $$ with base cases $T(0) = 4$ and $T(1) = 3$. How do I solve such a recurrence?
1
vote
1answer
46 views

Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$

Given is the following recurrence relation: $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$ where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$. I'm ...
1
vote
2answers
46 views

Deriving the average depth for a randomly generated binary search tree

If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken ...
0
votes
1answer
81 views

Coin Change Problem Recurrence Relation with one parameter

I have been looking through the recursive formulation for the coin change problem here and am wondering if it is possible to define the function $ C(N, m) $ in one parameter as $C(N)$, therefore not ...
-1
votes
2answers
38 views

Using Iterative method to find recurrence relation vs Master Theorm

I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem. $$\begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &=...
1
vote
2answers
213 views

Solving T(n)=T(n−1)+2T(n−2) using substitution

I am trying to solve the following Recurrence relation using substitution method and I am stuck almost half way. I know the answer is 2^n but I can't reach it. At first, my question is: Who decicdes ...
1
vote
1answer
23 views

Big-Oh vs Theta in recurrence tree method

I am solving this problem from here. The given relation is $$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$ The solution via recurrence tree method is given as: The zeroth level has a single node ...
1
vote
2answers
66 views

Big-O Solving Recurrence Relation by iteration with fractions

I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
0
votes
2answers
24 views

Which one is the correct way to change functional notation while solving recurrence relation?

In CLRS 3rd edition P. No 86, the relation $T(2^{n}) = 2T(2^{n/2}) + n$ is changed to $S(n) = 2S(n/2) + n$ My first question is, why we can change any recurrence relation like this? And, ...
0
votes
1answer
32 views

Optimizing the problem

I have a recurrence relation: f(a,b) = f(a-1,b)+f(a-2,b-1)+f(a-1,b-1) with conditions: f(0,0)=1, f(a,0)=1, f(0,a)=0, f(x,1)=2*x where the constraints: 1<=a<...
0
votes
1answer
26 views

Finding recurrence relations for dynamic programming algorithms

Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...
3
votes
3answers
118 views

How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem) [duplicate]

I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.
0
votes
1answer
23 views

Is any State Space Tree always Binary Tree?

A backtracking algorithm generates, explicitly or implicitly, a state-space tree. Introduction to the design & analysis of algorithms / Anany Levitin I wonder that whether the saying ...
0
votes
1answer
70 views

Show that $T(2^n) = \Theta(3^n)$ [duplicate]

We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?
1
vote
1answer
80 views

Answering questions about the recurrence of certain aspects of an algorithm

I am thoroughly confused by a problem that was brought up in class: Given the following pseudocode for a function RANDOM which generates a random number based off of recursion: ...
1
vote
1answer
60 views

Optimal substructure and dynamic programming for a variant of the rod cutting problem

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following. Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the ...
1
vote
1answer
74 views

Solving Recurrences Using Master Method [duplicate]

Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences: $T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$ $T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$ $T(n) = 2T(\frac{...
1
vote
1answer
48 views

Master's theorem

Is Master's theorem applicable on $T(n) = 2 T(\frac{n}{2})+n\log n$ ? I got this doubt from here: https://gateoverflow.in/227814/introduction-to-algorithms
0
votes
1answer
48 views

How to find closed form solution of linear recursion using recursive tree method

I want to be able to find closed form runtime solution for recursive insertion sort which looks something like this $$T(n)=\begin{cases} 1 &\text{if }n=1,\\ T(n−1)+3n &\text{...
3
votes
1answer
33 views

Is there a difference between using $n$ and $\Theta(n)$ in recurrences?

Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).
2
votes
2answers
32 views

Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$

I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved iteratively and I get totally clueless after two iteration.s I've to find tight bound ...
1
vote
3answers
89 views

Time complexity of function vs return value

I came across following problem: Find the time complexity of below recurrence relation: $T(n)=\begin{cases} & 2T(n/2)+C; & n>1\\ & C;&n=1 \\ \end{cases}$ The solution ...
3
votes
3answers
108 views

Solving $$f(x, k) = f(x, k-1) + f(x-1, k-1) + \dots + f(1, k-1)$$ in terms of $x$

I'm having trouble determining the complexity of an algorithm. Let's say the number of operations of my algorithm is described by $$f(x, k) = f(x, k-1) + f(x-1, k-1) + f(x-2, k-1) + \dots + f(1, k-1)$$...
1
vote
1answer
147 views

quicksort recurrence relation

In Concrete Mathematics Textbook by Donald Knuth and Oren Patashnik , ch.2 Sum ,sec2.2 He wrote: The average number of comparison steps made by quicksort when it's applied to $n$ items in random ...
1
vote
4answers
1k views

How to solve T(n)=2T(√n)+log n with the master theorem?

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?
2
votes
1answer
24 views

How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?

I am trying to find $T(n)=O(f(n))$, where $$T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right],$$ where $m\in\{1,2,\ldots,n\}$. Is it possible to find $f(n)$ such that $T(n)=O(f(n))$? I started to fix $m=n/2$...