Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
628
questions
0
votes
1answer
28 views
Iteration Vs Induction Method
I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit ...
3
votes
1answer
28 views
Approximation of rational sequences via linear recurrences of small order
I wish to approximate a sequence of rational numbers using a linear recurrence of order $k$ for some small $k$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact ...
0
votes
1answer
46 views
What is the asymptotic bound for $T(n)= 3T(\sqrt[3]{n})+n^3$?
What is the asymptotic bound? How do you get to the result?
$$T(n)= 3 \cdot T(\sqrt[3]{n})+n^3$$
0
votes
1answer
60 views
How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?
Can somebody help me with this recurrence please?
$T(n)=4T(\sqrt{n}/3)+(\log n)^2$
-2
votes
0answers
91 views
Find the number of additions in a recursive relation of two variables
Consider following recursive relations:
$$ F(i,0)=\begin{cases}
F(i+1,0) + F(i+1,1) & \text{ if } i<n,\\
0 &\text{otherwise}\\
\end{cases}$$
$$ F(i,1)=\begin{cases}
2F(i+1,0) + F(i+...
1
vote
1answer
25 views
Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$
What is the asymptotic rate of growth of the following recurrence relation?
$$
f(x) = \begin{cases}
8f(x/2) + Θ(1) & \text{ if } x^2 > M, \\
M & \text{ if } x^2 \leq M.
\end{cases}
$$
Here ...
2
votes
0answers
44 views
Two dimensional recursive function in $O(\log n)$ time complexity
It is well known that a recursive sequence or $1$-d sequence can be calculated in $O( \log n)$ time given that it has the form
$$a_n=\sum_{k=1}^{n} C_ka_{n-k},$$
where $C_k$ is a constant. Examples ...
1
vote
1answer
33 views
How to solve recurrence of a binary tree
I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.
This function calculates both the height and if its a balanced tree.
...
1
vote
2answers
62 views
Solving constants in the recursive term with master theorem
We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the ...
1
vote
1answer
62 views
Recurrence $T(n) = T(n - \log n) + 1$
Given recurrence relation : $$
T(n) = \begin{cases}
T(n-\log n) + 1 & \text{if } n \ge 1,
\\
1 & \text{otherwise.}\\
\end{cases}
$$
To find asymptotic order of $T(n)$ i do as follow:...
-1
votes
1answer
40 views
Time complexity a recursive function [duplicate]
Suppose given recurrence relation
$$T(n)=T(\sqrt{n})+T(n-\sqrt{n})+n$$ $$T(1)=O(1)$$
How we can find an order of above recurrence relation?
My attempt:
I read following post, but get stuck in ...
0
votes
1answer
32 views
Divide and conquer recurrence relation
I have divide and conquer problem and below is the recurrence relation for it
$$\begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\
t(n) &= a\cdot t (n/4) + O(n^2)
\end{align}$$
...
0
votes
1answer
50 views
How to calculate the average depth of a binary tree?
My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach ...
0
votes
0answers
19 views
Recurrence relation of an algorithm
how can I know what are the recursive calls of this algorithm ?
in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation.
Here is the algorithm :
2
votes
2answers
134 views
Asymptotic order of a recursive function
\begin{gather*}
T(n)=T(\frac{n}{\log n})+O(1)
\end{gather*}
\begin{gather*}
T(1)=O(1)
\end{gather*}
I try to use substitution method to solve $T(n)$, but because of $\log n$ get stuck. Can we use ...
1
vote
2answers
40 views
-1
votes
2answers
51 views
Accurate height of recursion tree for given recursion
We are trying to find height of following recursion formula in terms of $n,k$:
\begin{gather*}
T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk
\end{gather*}
\begin{gather*}
T(n,1)=T(1,k)=O(1)
\end{...
0
votes
3answers
88 views
Solving a recurrence of uneven subproblems without Akra-Bazzi
I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$
I observed it ...
1
vote
1answer
60 views
Solving recurrence relation for running time of combination formula
I'm trying to solve the following Time complexity recurrence relation:
$T(n,k)=T(n-1,k-1)+T(n-1,k)+1$
that come from following code:
...
1
vote
1answer
38 views
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$
My approach with recurrence tree:
$n \sim n\log(n)$
$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$
$\frac{n}{4} \...
2
votes
1answer
35 views
Showing asymptotic lower bound on log of recurrence
I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows:
$T(1) ...
1
vote
1answer
19 views
Which of the following is a more appropriate complexity for this reccursive function?
Given the following recurrence relation:
\begin{gather*}
h(A) =
\begin{cases}
0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\
1+h(A-1),\text{ }\text{ }A\text{ is odd} \\
1+h(\frac{A}{2}),\...
1
vote
1answer
24 views
On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$
Consider the recurrence
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$
What is the condition on $a,b$ that guarantees $T(n)=O(n^c)$?
With substitution I get
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})...
0
votes
0answers
19 views
Computer Science [duplicate]
I am trying to solve the following problem to find big-theta. I am having a lot of trouble, if anyone can help!
T(n)=8T(√n)+log^2(e^n)?
The logarithm is base 2 and is squared.
0
votes
0answers
44 views
Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$
Lets define function $T(n)$ as
\begin{align*}
T(1) &= T(2) = 1\\
T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\
\end{align*}
Does $T(n)=O(\log(n))$? I have no idea how to ...
2
votes
2answers
44 views
How to solve recursion T(n) = T(n/3) + T(2n/3) + n?
$T(n) = T(n/3) + T(2n/3) + n$
How can I solve this recurrence formula?
-2
votes
2answers
44 views
Solve T(1) = 1 T(n) = T(n-1) + n^2 for n ≥ 2
I am not able to solve the following recurrence relation:
$$
T(n) = \begin{cases}
T(n-1) + n^2 & \text{if } n \ge 2,
\\
1 & \text{otherwise.}\\
\end{cases}
$$
How do I start?
0
votes
0answers
16 views
Starter book on solving recurrences
I am having problems with algorithms, particularly solving them using recurrence. can anyone suggest an easy to understand basics introduction to this so that I can get my head around the concept.
1
vote
2answers
64 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
60 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
38 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
36 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
41 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
50 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
31 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
35 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
63 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 ...
2
votes
1answer
39 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
31 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
312 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
152 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
44 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
43 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
47 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
50 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
46 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
116 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}^{...
