Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
603
questions
1
vote
2answers
58 views
Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
1
vote
1answer
53 views
How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$
Consider the following recurrence relationship.
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
2T\left(\...
2
votes
2answers
33 views
How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?
I am interested in the asymptotic bounds of the following recurrence:
$$T(n)= T(n - 1) + \frac{1}{n\log n}$$
with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much ...
3
votes
1answer
28 views
Karger's min cut and tips on bounding nonlinear recurrences
I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a ...
0
votes
1answer
35 views
Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)
I am doing an exercise which says that this is true:
T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)
So I tried to solve it by substitution, but I am getting a non-sense result.
So would really ...
1
vote
1answer
37 views
Find the recurrence relation for the following algorithm
The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation.
\begin{align}
&\text{SORT}(A[0\dots n-1])\colon\\
&\quad \text{...
-1
votes
1answer
30 views
help understanding the recurrence relation of an algorithm
I have the following code which I have to figure out the recurrence relation, but I am having a bit of a trouble understanding what the algorithm does exactly.
...
0
votes
1answer
28 views
How to work out the odd case?
I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to ...
3
votes
1answer
61 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)^{\...
0
votes
0answers
14 views
How to set up a recurrence relation to analyze number of execution of the basic operation of this algorithm? [duplicate]
This an algorithm to count inversions in an array, this is a divide and conquer algorithm, I ...
1
vote
1answer
30 views
Master theorem: $T(n)=10T(n/9)+n\lg(n)$
I am told to solve the recurrence
$$T(n)=10T(n/9)+n\lg(n)$$
using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $...
1
vote
1answer
29 views
Applying Akra–Bazzi with an unbounded number of summands
The Akra–Bazzi method handles recurrences of the form
$$
f(n) = \sum_{l=1}^k a_l f(n/b_l).
$$
Does it work when then number of $a \cdot f(n/b)$ is not finite, meaning that we have a sum that depends ...
0
votes
2answers
36 views
Solving recurrence $T(n) = T(n - 1) + n$ with substitution method
How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method?
I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$:
$$T(n) \leq O(n^2) \\ \leq c(n-1)^2+n ...
1
vote
1answer
40 views
Solving the recurrence formula $T(n) = 3T(n/2)+n^2$
What is the solution of the following recurrence?
$$
T(n) = 3T(n/2) + n^2, \quad T(1) = 0.
$$
I cannot use the master theorem since I need to know the exact final expression, not just it's big O, ...
1
vote
2answers
36 views
Constant terms at each level of a recursion tree
In CLRS, exercise 4.4-5 the following question is asked:
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$
In my recursion tree, the ...
1
vote
2answers
25 views
Big theta notation in substitution proofs for recurrences
Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.
For example, on page 91, the recurrence
$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$
is written like so in ...
1
vote
1answer
39 views
Running time of a function $P$ calling itself via $P(P(n/2))$
int P(int n)
{
if (n==1)
return 1;
else
return P(P(n/2));
}
How will this function P(P(n/2)) be executed and what ...
1
vote
1answer
46 views
Evaluating $T(n)=2^n+4T(\frac{n}{2})$
$$T(n)=2^n+4T(\frac{n}{2})$$
I have started substitution for:
$$T(\frac{n}{2})=2^{\frac{n}{2}}+4T(\frac{n}{4})$$
$$T(\frac{n}{4})=2^{\frac{n}{4}}+4T(\frac{n}{8})$$
$$...$$
$$T(\frac{n}{4})=2^n+4[2^{\...
0
votes
1answer
49 views
Recurrence relations and the Master Theorem
Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation:
T(n) = 99T(n/100) + log(n!)
I'm trying ...
0
votes
1answer
39 views
substitution method on T(n) = T(floor(n/2)) + n recurrence
While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.
Why we assumed that this inequality holds for all ...
1
vote
1answer
22 views
How can recursion tree split a problem into smaller pieces that do not add up?
If I have a recurrence equation:
$$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$
It says it splits a problem of size n into 3 subproblems of size n/4. Then it keeps splitting it until the problem size at ...
0
votes
1answer
60 views
Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method
I'm trying to solve this recurrence. I applied the iterative method:
$$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{...
1
vote
1answer
47 views
Solving $T(n) = 4T(n/2) + n^3$ with substituton method
I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, ...
0
votes
2answers
36 views
Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$
I need to prove that the following recurrence relation is $O(5^n)$:
$$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$
And $T(n)=\Theta(1)$ for $n\le 9$.
I am trying induction, and proving that there ...
0
votes
1answer
54 views
Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$
The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
0
votes
0answers
8 views
What case of the master theorem of this recurrence?
I have a question abou this recurrence:
$T(n) = 27T(n/3)+n³/ \log n$
By Master Theorem. will be: $T(n) = \theta(n^3)$ or $T(n) = \theta(n³ \log \log n)$ ?
1
vote
1answer
68 views
Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$
I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$.
However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence ...
0
votes
1answer
32 views
Need help with recurrence relation and postcondition of a function
I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
...
0
votes
1answer
28 views
Doing induction on recurrences correctly
I have $$T(n)=T(n-1)+n^{2}$$
And I know, by drawing the recursion tree that this is $\Theta (n^{3})$
However, if I try claiming that it's $O(n^{2})$ through induction:
$$T(n)\le c(n-1)^{2}+n^{2}\le cn^...
2
votes
1answer
55 views
Matrix chain multiplication recurrence and its solution
We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$.
In the classical matrix chain multiplication problem, we wish to minimize the total ...
1
vote
1answer
34 views
What's wrong with this substitution for master's method
I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method:
$$T\left(n\right)=T\left(n-1\right)+n^2$$
I did
$$S\left(2^n\right)=S\left(2^{n-1}\...
0
votes
0answers
16 views
Write recurrence for cost minimization
So I am trying to find the recurrence for this problem but I feel like it is missing something.
An ice cream shop is looking to minimize their operation costs, under the given constraints:
They are ...
0
votes
2answers
52 views
Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$
Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where
$$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$
The base case for $n=1$ seems ...
0
votes
2answers
111 views
Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$
Solve the following recurrence-relations:
my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same ...
0
votes
1answer
45 views
Recurrence relations and induction: guessing the right bound
I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$
This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-...
0
votes
2answers
74 views
Failing to solve a recurrence by induction
My question is strongly related to the one asked here:
How do I show T(n) = 2T(n-1) + k is O(2^n)?
$$T(n)=2T(n-1)+1$$
Going with the steps, I reached the point where:
$$c*2^{n}\geq c*2^{n}+1$$
which ...
-2
votes
1answer
104 views
Solving $T(n) = 16T(n/2) + n$
I am trying to solve the following recurrence relation :-
$T(n)=16T(n/2)+n$ using masters theorem. I got $\Theta (n^2)$ (Which matched the first case in the theory) which is wrong, any help with this ...
2
votes
1answer
29 views
Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $
$$\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $$
I've found so many similar questions but I couldn't understand any of the answers explanations. When I try to draw a recurrence tree, I see that each '...
1
vote
1answer
45 views
How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$
I try to find tree height such that first i define:
$H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$
then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree ...
0
votes
0answers
17 views
Upper bound for reccurence relation with two variables, with linear dependency between them
Given the following reccurence relation:
$$T(M,k) = T(M-1,k)+T(M-2,k-1)$$
where $T(0,k)=0, T(1,k)=1, T(M,1)=1$
I have $M^k$ as a general upper bound for $T(M,k)$.
Now, suppose I want to give an upper ...
0
votes
1answer
77 views
prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $
i want to prove upper bound of the following recurrence $ T(n) =T(n-\sqrt{n})+1 $ is $ O(\sqrt{n})$.
2
votes
1answer
41 views
Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $
What's the (asymptotic) solution of the following recurrence?
$$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$
I tried to solve this with generating functions to find an accurate bound.
0
votes
0answers
45 views
What is the time complexity of this recurrence relation?
T(n) = 12 T(n/(logn)^2) + nlogn
How to find the value of b using masters theorem. I think with the help of masters theorem we can't solve this. Is there any other method ?
0
votes
1answer
56 views
Is “backward substitution” and “backtracking” the same thing?
From my limited knowledge, they both are related to solving recurrence relation.
Solving recurrence relation using backward substitution
Solving recurrence relation using backtracking
Can the terms ...
0
votes
0answers
28 views
Solving a recurrence in which $n$ decreases by $\sqrt{2n}$
I'm trying to solve the recurrence
$T(n)= 2T(n-\log f(n))+ f(n)$, where $f(n) = 2^{\sqrt{2n}}$,
using the master theorem. Which case applies here?
0
votes
1answer
16 views
How do I work out the recurrence relation of the given function?
I am looking to find the recurrence relation (RR) of the fnA(), but I am unsure how $n$ is to be represented.
(More specifically, I am trying to work out the ...
1
vote
2answers
78 views
Recurrence $f(n+1)=2f(n)-f(n-1)$ with initial values $f(0)=0,f(1)=1$
How do I solve the following recurrence?
$$
f(0) = 0, \quad f ((1)) = 1, \quad f((n+1)) = 2*f(n) - f(n-1).
$$
-1
votes
1answer
239 views
Solving T(n) = 3T(n/3)+sqrt(n) using master method
I want to know how to find the complexity of this recurrence.
0
votes
1answer
44 views
Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$
I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term.
We can write $$\frac{T(n)}n=...
1
vote
1answer
47 views
Difficult reccurence with two variables
My question is a follow-up for the following thread: Solving unusual recurrence with two variables
I baisically have the same reccurence relation but with a small change---
$$T(n,k) = T(n-1,k)+T(n-m,k+...
