Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
2
votes
1answer
316 views
Solving recurrence relation with minimum and factorial
I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N_+\times\Bbb N_+$.
$T(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq 2(n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\...
1
vote
1answer
100 views
Recurrence with Minimum
I need to solve the following recurrece:
$T(n,m)=\begin{cases}
1, & m\leq 2(n-1)!\\
\min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else}
\end{cases}$
Note:...
2
votes
1answer
47 views
solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method
How can I solve $$T(n)=T(n-2)+\frac {d}{2}n^2$$
I couldnt find $d$ (dont know if I have to) and after 3 iterations I got to $k= \frac{n-1}{2}$
but had trouble to continue.
2
votes
2answers
41 views
Number of possible heaps on $\{1,…,2^h-1\}$
Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.
Definition
A binary tree ...
0
votes
1answer
31 views
Trouble finding what this recurrence solves to [duplicate]
I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$
I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
2
votes
1answer
53 views
What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ [closed]
Problem:
Find the closed-form expression for$$
T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1
\tag{1}
$$where $T_1 = 1 .$
Calculating this sum I came up with the following result:
$$
T_n = 8^{\left(...
2
votes
1answer
50 views
How to prove a bound function for a sequence of numbers?
Let $G_n$ be defined by
$$G_n = \begin{cases} 1 & n=0 \\
2 & n = 1 \\
3 & n = 2 \\
4 & n = 3 \\
2G_{n-1}-2G_{n-3}+G_{n-4} & n\geq4
\end{cases}$$
How can I prove that $f(n) = n$...
1
vote
1answer
38 views
Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$
Consider the recurrence
$$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$
I tried to solve this as follows. First, I found the homogeneous solution:
$$
a_n^{(h)} = r^2 - 3r + 2r \\
(r-2)(r-1) = 0 \\
...
0
votes
0answers
36 views
How can I prove the linear time search algorithm takes O(n) time? [duplicate]
The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
0
votes
0answers
22 views
Meaning of polynomially larger, / smaller and meaning of polynomial larger / polynomial smaller
Hi I have spent the last two hours trying to find a general definition for both of these terms, but it seems like in computer science, people do not really agree on definitions. And I haven't even ...
0
votes
1answer
49 views
Closed form solution of $T(n) = 5T(n-1) + n^2$ [duplicate]
How to find the closed form solution of this equation? Is there a repeatable pattern for solving this equation?
$$T(n) = \begin{cases}
1 & n = 1\\
5T(n-1) + n^2 & \text{otherwise}
\end{cases}$...
2
votes
2answers
71 views
Finding recurrence relation for running time of an algorithm
I am pretty new to this, consider the following algorithm:
...
0
votes
0answers
21 views
Substitution method for $T(n) = 2T(7n/10) + O (1)$ [duplicate]
I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method.
I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.
3
votes
2answers
75 views
How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?
The recurrence I have is
$T(n) = 2T(\sqrt{n-1} + 2) + 1$
I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm ...
1
vote
0answers
80 views
What are the asymptotic bounds (upper bound on time complexity) of the following function?
I am trying to find the upper bound on time complexity of the recursive function defined by the following equation:
$$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
0
votes
2answers
56 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)$...
3
votes
0answers
44 views
Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm
I have a graph algorithm that runs in:
$$ T(n, m) = \begin{cases}
c_1 & n \leq 2 \lor m = 1\\
T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + ...
1
vote
3answers
71 views
Solving $T(n)=4T(n/2)-1$ without using the master theorem [duplicate]
How can I solve the following recurrence without using the master theorem?
$T(n)= 4T(n/2)-1$ for $n>4$ and $T(n)=5$ for $n\le 4$, $n$ is a power of $2$.
0
votes
3answers
103 views
Solving recurrence equation $T(n)=T(n^{2/3})+17$
How can the following recurrence equation be solved by one of three main ways:
$$T(n)=T(n^{2/3})+17$$
I have tried solving it by the iteration way. However it does not work for me since I can't find ...
0
votes
2answers
49 views
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
If I have a recursive function like this for example (This is just an ...
1
vote
4answers
140 views
Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10
The solution is to find the upper and lower bounds from:
2T(n-2) < T(n) < 2T(n-1) + 10
So I have to find
...
2
votes
1answer
53 views
Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences
Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log_2 n)$-time 1. However, there doesn't seem to be a lot of resources on generalizing his idea ...
0
votes
0answers
16 views
Solve Recurrence $T(n) = T(pn) + T((1-p)n) + \Theta(n)$ [duplicate]
For $0 < p < 1$, how can you solve the recurrence $$T(n) = T(pn) + T((1-p)n) + \Theta(n)$$ using the substitution method. My guess is $T(n) = O(n \log n)$, but plugging this guess in leads to a ...
1
vote
1answer
29 views
Solving the recurrence $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $
I need to solve the following recurrence relation: $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)...
7
votes
2answers
79 views
The recursion $T(n) = T(n/2)+T(n/3)+n$
I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).
Using induction, I found that $T(n) = O(n\...
1
vote
0answers
31 views
Prove that the upper bound for T(n)=T(an)+T(bn)+O(n) is O(n) [duplicate]
While learning Median of Medians algorithm i came across the following lemma ;
"For any recurrence of the form $T(n)<=T(an)+T(bn)+O(n) $,
if $(a+b)<1$ the reccurence will solve to $O(n)$"
(...
2
votes
1answer
38 views
Solving T(n) = T(n-1)*T(n-2)
So, this is how I solved
$\displaystyle
T(n-1) \approx{} T(n-2)
$
$\displaystyle
T(n) = T(n-1)^2
$
Add log in both sides
$\displaystyle
log(T(n)) = 2log(T(n-1))
...
1
vote
1answer
47 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
64 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
235 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
32 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
35 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
27 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
41 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
68 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
39 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
107 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
363 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) = ...
3
votes
1answer
56 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
350 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
70 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
28 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
49 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
254 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
...
1
vote
1answer
231 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
68 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
67 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
98 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
49 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) = ...
