Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
653
questions
0
votes
0answers
17 views
Intuition behind : recursive algorithm takes exponential time
So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
-3
votes
0answers
10 views
recurrence equation 2T(n-4) + n^2 solution?
need help solving this equation.
the general equation I end up with:
2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
0
votes
2answers
30 views
How to solve $T(n) = T(27n/9) + n^3$ with substitution method
I'm trying to solve this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps:
$$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$
How can I continue?
1
vote
1answer
23 views
Finding time complexity $T(n) = 2^n T(n/2) + n^n$
I am applying substitution method to find the time complexity of the following recurrence relation. But I am having difficulty solving it past a certain point.
$$T(n) = 2^n T(n/2) + n^n$$
After ...
0
votes
2answers
34 views
Regularity condition for cases 1 & 2
My question concerns the version of the Master Theorem described in CLRS and in this handout.
I already understand the following:
If the regularity condition in case 3 does not hold, then we can't ...
1
vote
1answer
31 views
Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
-1
votes
0answers
22 views
How to solve the recurrence relation T(n) = T(n/2) + n^2 using recursion trees?
I drew the recursion tree but I can't seem to make a conclusion as to what the total amount of work done is.
1
vote
1answer
24 views
Given a source and destination, find the path with minimum stress level in a Graph
I faced this problem in a hiring challenge which is now over.
I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
0
votes
1answer
40 views
How to solve $T(n) = 2T(n/4) + n \log n$ with substitution method?
I am trying to solve this recurrence with substitution method. I guess $T(n) = \Theta(n \log n)$ (with Master Theoreme). Can someone show me how to demonstrate the upper bound $T(n) = O(n \log n)$?
0
votes
1answer
34 views
Solve $T(n) = 3T(\frac n3 + 5) +\frac n2$
Given recursive equation, $T(n) = 3T(\frac n3 + 5) +\frac n2$
$$
\begin{align}
T(n) = 3T(\frac n3 + 5) +\frac n2 \tag{1} \label{1} \\
\lt 3T(n- 15) +\frac n2\\
\lt 3 \left(3T\left(\frac{(n- 15)}{3} +5 ...
3
votes
1answer
47 views
Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
I am trying to solve the recurrence $$T(n) = T(n-1) + (-1)^nn, \quad T(0) = 1.$$
I'm stuck in the summation:
\begin{align}
T(n) &= T(n-1) + (-1)^n n \\ &=
T(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ ...
3
votes
3answers
198 views
Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
For the following recurrence relation:
$$T (n) = T (n/2) + n(2 - \cos n)$$
I see it based on values of $\cos$ function given that it output values in range, but this does not seem to have anything to ...
0
votes
0answers
34 views
Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]
How to solve the below relation?
$$
T(n) = T(0.01n) + T(0.99n) + cn
$$
This will not be a balanced tree.
For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$.
I ...
1
vote
1answer
46 views
Solving T(n,m) = 3n + T(n/3,m/3)
I have the below recurrence:
\begin{align}
T(n, 1) &= 3n \\
T(1, m) &= 3m \\
T(n, m) &= 3n + T(\tfrac{n}{3}, \tfrac{m}{3})
\end{align}
How to get a tight asymptotic bound for $T(n, n^2)$ ...
0
votes
2answers
58 views
Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$
This is not a difficult problem, but I would like please to discuss with you how I solved it:
Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$, $T(1)=2$. What is the value of $T(9)$? This can ...
1
vote
1answer
26 views
$T(n/2 +1)$ substitution in recurrence relation
How to find the recurrence relation using domain range substitution method for the below:
$$
T(n) = 2T\left(\frac{n}{2} +1\right) + n -2
$$
I am unable to get a pattern with this relation as it is ...
1
vote
1answer
50 views
Solving recurrence relation with square root by reduction
This question has already been asked, but I still cannot understand how the substitution makes sense in the recurrence equation $$T(n)=2T(\sqrt{n})+1$$
Following the logic:
Substitute $n$ for $2^m$. ...
0
votes
0answers
23 views
Solving the recurrence using Master or Akra-bazzi theorem
I was trying to use Akra-bazzi theorem for the recurrence equation below for time complexity, but I do not get any value of p that satisfies the condition $\sum a_i b_i^p = 1$ for the equation below.
...
3
votes
2answers
102 views
Recurrence and Time complexity
I am having problem solving this recurrence. Can anyone help me with this please:
$$ T(n) = 2(T(\sqrt n))^2 , T(1) = 4. $$
1
vote
0answers
31 views
Is there a class of recurrence relations that can't be solved using the substitution method?
Is there a class of recurrence relations that can't be solved using the substitution method? Let me explain the motivation behind this question by an example.
Consider the recurrence relation $T(n) = ...
0
votes
0answers
10 views
Video lectures showing the way to solve recurrence relations using Akra-Bazzi method, taking ample examples
After reading about the Akra-Bazzi method of solving recurrence relations from the chapter notes of the CLRS text (p. 112-113 of [3e]), I felt that the method is a bit subtle.
Even the authors say ...
0
votes
0answers
52 views
Merging the submatrices' time complexity in matrix multiplication
This is a problem of CLRS:
What is the largest $k$ such that if you can multiply $3 \times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply
$...
0
votes
2answers
34 views
recurrence with exponentials
I am trying to figure out on how to approach the problem on finding proving the asymptotic of an exponential recurrence. It is described as such:
t(n)=4t(n/2)+2^n with t(1)=1 for n>=5
From what I ...
0
votes
0answers
16 views
What is the return value of the following code R(n) = 2R(√n) + n?
Algorithm rec(n)
{
if (n ≤ 2)
return 1
else
{
return (2*rec(√n) + n)
}
}
Return value recurrence relation, I want to find the exact value and not ...
0
votes
1answer
74 views
Multiplying two integers by dividing each into 3 parts
Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
1
vote
0answers
85 views
0
votes
0answers
59 views
Total work done at a recursion tree level
In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is
$$a^k \times O\left(\frac{n}{b^k}\right)^d$$
where $a$ is the branching ...
1
vote
1answer
51 views
Solving $T(n) = 2T(n/2) + \log n$ using the master theorem
Is there a substitution, so that the following recurrence relation can be solved using the given version of the master theorem?
$$ T(n) = 2T(n/2) + \log n $$
Let $a,b \in \mathbb{N}$, where $b > 1$...
2
votes
1answer
60 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
32 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 ...
2
votes
2answers
91 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
3answers
136 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
2answers
103 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
53 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
70 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
97 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
70 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
42 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
46 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
157 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
20 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
159 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
54 views
-1
votes
2answers
63 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
126 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
70 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
2answers
82 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
2answers
54 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
20 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
29 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})...
