Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
656
questions
0
votes
1answer
39 views
Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$
I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way:
$n = 2^k$
$2^{\frac{2}{k}}\cdot T\left(2^k\right)+\...
2
votes
1answer
1k views
Can we solve a "very" exponential recurrence?
Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ?
Thanks!
2
votes
1answer
108 views
+50
Skyline problem with triangular buildings
This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites.
The following are two variations from the usual Skyline problem:
Report ...
0
votes
0answers
23 views
Space complexity for divide-and-conquer
Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class.
Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
0
votes
1answer
34 views
Solving a recurrence relation with two variables
I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function.
First of all I think the relation looks like ...
1
vote
1answer
21 views
Solve recurrence where the base case's time complexity is a function of the original input size
I'm trying to analyse the time complexity of the following algorithm for generating the power set:
...
0
votes
0answers
23 views
Intuition behind : recursive algorithm takes exponential time [duplicate]
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 ...
0
votes
2answers
45 views
How to solve $T(n) = 27T(n/9) + n^3$ with substitution method
I'm trying to bound 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
34 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 ...
1
vote
2answers
45 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
44 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
vote
1answer
43 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
52 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
36 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
48 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
246 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
35 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
48 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
70 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
29 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
52 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
26 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
119 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
33 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
11 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
42 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
86 views
0
votes
0answers
65 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
63 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
64 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
34 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
3answers
105 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
172 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
104 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
57 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
100 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
108 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
71 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
44 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
50 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
182 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
21 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
164 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
66 views
-1
votes
2answers
66 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
141 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
73 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:
...