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