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
59 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
21 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
44 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
60 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
69 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
32 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
48 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
43 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 ...
0
votes
0answers
23 views

Solving Recurrence relation using Master Theorem

There is a recurrence relation like $T(n)=mT(n/2)+cn^2$ To solve this recurrence relation I am using Master Theorem. As per master theorem here a = m, b = 2, k=2 ,p=0 So $b^k= 2^2 = 4$ Now, ...
0
votes
0answers
40 views

What's the lower bound of the height of an unbalanced recursion tree?

I don't understand what's going on here. People say, longest path should yield an upper bound of tree height while shortest path should yield a lower bound of tree height. Please take a look at https:/...
0
votes
0answers
19 views

Understanding the logic of algorithm runtime

I'm trying to understand the runtime of this code: def f(n): if (n <= 1): return 1 else return f(n-1)*f(n-1) + f(n-1) At first, my logic said ...
1
vote
2answers
30 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
57 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
33 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
81 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
20 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
47 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
23 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
20 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
115 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
22 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
54 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
76 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
47 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
63 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
38 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
31 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
31 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
81 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
85 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
557 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$...
0
votes
1answer
117 views

Solving recursion $T(n)=2T(n/2) +2/\log(n)$

everybody, I'm trying a whole day to compute this recursion. I will be grateful if someone can try and solve it $$T(n)=2*T(n/2)+2/\log(n),$$ where $\log n$ is the logarithm to the base 2 - of ...
1
vote
1answer
36 views

Recurrence Substitution Method with multiple givens

Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$ Given $T(0)=3$ and $T(1)=5$ I kind of understand it with only one given and one recurrence call by expanding the call using what is ...
2
votes
2answers
40 views

Time complexity calculation

I was calculating the time complexity of the following recurrence relation given that T(1) = 1 : T(n) = 2T(n/2) + Logn I was calculating the value and this is where I reached: T(n) = logn + 2log(n/...
1
vote
1answer
62 views

Solve T(n)=T(√n)+ n using substitution method

I am confused how to solve this recurrence equn. after a particular step (step involving ? in the picture) (Plz help me solve the question with same method which I have used and correct if any of the ...
2
votes
0answers
72 views

Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
0
votes
1answer
24 views

What is time complexity in this case?

I have the recurrence of the form T(n) = T(n/2) + O(n) This can be solved using master's theorem and if i use the results of the theorem, the recurrence evaluates to a time complexity of O(n). ...
1
vote
0answers
16 views

Question on Recurrence $T^2(n) = T(n/2) * T(2n) - T(n) * T(n/2)$

Need help solving this recurrence: $T^2(n) = T(n/2) * T(2n) - T(n) * T(n/2)$
3
votes
1answer
55 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 ...
4
votes
1answer
42 views

Recursion in pi-calculus

In the book by Sangiorgi and Walker ("The $\pi$-calculus: A theory of Mobile Processes"), Subsection 3.2 is devoted to recursion. They state the following constraint (pages 132-133): "The ...
3
votes
2answers
47 views

Solving recurrences by substitution

I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method. Given the recurrence: $$ T(n) ...
0
votes
2answers
203 views

Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers

This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2). Is it possible to do this question if we entirely want to skip ...
0
votes
0answers
29 views

Solving $T(n) = \frac{1}{n}(T(0)+T(1)+…+T(n-1)) + cn$ for all $ n \geq 1$ [duplicate]

Solving $T(n) = \frac{1}{n}(T(0)+T(1)+...+T(n-1)) + cn$ for all $ n \geq 1$ Subbing few numbers in we get $T(1) = T(0)/1 + c(1)$ $T(2) = \frac{T(0)+T(1)}{2} + c(2) $ Which is kind of going ...
3
votes
1answer
166 views

Time Complexity: Intuition for Recursive Algorithm

I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book. The first example problem presented there is Rod Cutting (15.1). Given a rod ...
0
votes
0answers
21 views

Complexity of $T(n) = 4T(n/2) + n^2 \cdot log_2 (n)$ [duplicate]

After constructing the recursion tree i concluded a cost of $n^2\cdot log_2(n)-i\cdot n^2$ per level. So my total cost is: $$\sum_{i=0}^{log_2(n)}n^2\cdot log_2(n)-i\cdot n^2$$ $$=(log_2(n)+1)\cdot ...