Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
679
questions
0
votes
0
answers
19
views
Prove a Predicate is Primitive Recursive
Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula.
Prove ...
-2
votes
2
answers
27
views
I need to sort out the theta complexity for lg(n^(1/2))
Can you help me find the theta complexity for lg(n^(1/2))?
0
votes
1
answer
35
views
Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2
I am trying to solve
T(n) = 4*T(n/4) + n*[log(n)]^2
I decided to use Master Theorem so I found a,b=4 and logb(a)=1.
I thought that 3rd case is the solution but I ...
-3
votes
0
answers
33
views
Solving T(n) = 4T(9n/18)+n² [duplicate]
I am trying to solve a recurrence using substitution method. The recurrence relation is:
T(n) = 4T(9n/18)+n²
How can I find tight asymptotic lower bound (Ω-...
0
votes
1
answer
38
views
Does a closed formula exist for each recurrent formula?
I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the ...
- 11
1
vote
2
answers
54
views
Formal mathematical resolution for Recurrence Relations
let's suppose we've got a simple Recurrence Relation:
$$ T(n) = \begin{cases}
1 & n=1 \\
T(n-1) + \Theta(n) & \text{otherwise}
\end{cases}
$$
At lesson we've resolved it, but I ...
- 212
3
votes
2
answers
302
views
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Given the algorithm
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)
I defined a recurrence
$ ...
- 45
1
vote
1
answer
49
views
A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$
Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$.
That is, $(())$ has $n = 4, d = 2$. $()((())(...
- 11
2
votes
2
answers
56
views
Solving $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ with substitution method
The book I took this example from (Introduction to Algorithms, CLRS) wants to prove that the recurrence relation
$$T(n) = 2T(\lfloor n/2 \rfloor)+n$$
is
$O(n\lg n)$ using the so-called substitution ...
- 212
3
votes
2
answers
313
views
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Given the recurrence
$$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$
My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
- 337
1
vote
1
answer
46
views
Simplifying Notations in Recurrence Relation
In the CLRS book, section 4.4 they try to resolve the following recurrence:
$$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$
Later, they write the same recurrence as
$$T(n) ...
- 212
0
votes
1
answer
37
views
Recursive function - proof by induction
Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists.
I've encountered the following function:
$f([])=[]$ (empty list)
$f([x])=[x]$, for $x \in \Sigma$
$f(x:L)=f(L)$, for $x \in \Sigma$ and $...
- 1
2
votes
1
answer
56
views
Trying to understand the basic about recurrence trees
I have little background on recurrence trees, and I am working on the following exercise:
Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
- 187
0
votes
0
answers
41
views
Optimal substructure
Is optimal substructure lost when there are different functions in the recurrence relation?
Does optimal substructure require the construction of its solution only from subproblems of the same ...
- 145
1
vote
1
answer
36
views
Find the proper hypothesis for the substitution method for a recurrence problem
I'm trying to solve a recurrence problem using substitution method:
Given the following recurrence equation:
$
T(n) =
\begin{cases}
3 &n = 0 \\
3T(\frac{n}{5}) + T(\frac{n}{6}) + n&n ...
- 165
0
votes
0
answers
46
views
Solving recurrence finding theta of T(n)=T(log n)+1
$$
T(n)=T(\log n)+1
$$
$$
T(n)=\Theta(...)
$$
I want to find theta of $T(n)$. I tried the master theorem but failed.
2
votes
2
answers
42
views
Programmatically determine if a tie is possible in US elections
Problem 3.5 from book: "Algorithms for interviews".
There are 51 states (+ Washington DC), each with different amount of votes. Find the number of votes of each state here
Suppose there are ...
- 123
1
vote
1
answer
80
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
- 11
1
vote
3
answers
95
views
Solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I am trying to solve the recurrence
$T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I tried method I saw but I do not fully understand which looks like:
$T\left(n-1\right)\:=\:3T\left(n-2\right)\:+\:...
- 29
1
vote
1
answer
81
views
Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method
Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$.
I tried to form the Induction Hypothesis but didn't succeed in choosing the right one.
Try 1:
If we ...
- 45
1
vote
3
answers
52
views
Solve $T(n) = \frac78T(\frac78n) + \frac78n$
The recurrent function $T(n) = \frac78T\left(\frac78n\right)+\frac78n$ where $T(1) = 0$ and $n = \left(\frac87\right)^k$ represents the running time of an algorithm. How can I find a more simple form (...
- 11
0
votes
0
answers
28
views
Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?
I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks.
He said:
...
- 1
1
vote
2
answers
53
views
Tight bound for T(n) = T(n/2) + T($\sqrt{n}$) + n
I have seen examples of how to find the solve the recurrence for T(n) = T($\sqrt{n}$) + n, but how do we go about if there is another T(n/2) in there?
So I tried to unfold the recurrence out and this ...
- 21
0
votes
3
answers
60
views
Recurrence relation with O(loglogn)
I am trying to solve a recurrence relationship as follows:
T(n)=T(n^1/2)+O(loglogn)
I can solve the T(n^1/2) part quite easily, but I am completely lost as to what to do with an O(loglogn). I cant use ...
1
vote
2
answers
93
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)+\...
- 29
2
votes
1
answer
1k
views
Can we solve a "very" exponential recurrence?
Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ?
Thanks!
- 29
3
votes
1
answer
154
views
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 ...
- 225
0
votes
0
answers
97
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$ ...
- 101
0
votes
1
answer
58
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 ...
- 115
1
vote
1
answer
29
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:
...
- 123
0
votes
0
answers
24
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 ...
- 201
0
votes
2
answers
103
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
1
answer
128
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 ...
- 179
1
vote
2
answers
55
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 ...
- 11
2
votes
3
answers
75
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 ...
- 21
1
vote
1
answer
191
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 ...
- 13
0
votes
1
answer
76
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
1
answer
47
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 ...
- 459
3
votes
1
answer
52
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 \\ ...
1
vote
1
answer
82
views
What is the Runtime of this recursive algorithm?
I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
- 11
3
votes
3
answers
888
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 ...
- 459
0
votes
0
answers
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
1
answer
66
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)$ ...
- 11
0
votes
2
answers
89
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 ...
- 459
1
vote
2
answers
49
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 ...
- 35
1
vote
1
answer
74
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$. ...
- 11
0
votes
0
answers
33
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
2
answers
133
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
0
answers
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) = ...
- 61
0
votes
0
answers
14
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 ...
- 1,034