Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
559
questions
1
vote
2answers
62 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
45 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
26 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
40 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+...
1
vote
1answer
37 views
Solve Recurrence for $T(n) = 7T(n/7) + n$
I'm trying to solve the recurrence for $T(n) = 7T(n/7) + n$.
I know using Master Theorem it's $O(n\log_7n)$, but I want to solve it by substitution method.
At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^...
0
votes
2answers
45 views
Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$
I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.
$T(n)= 5T(n/4) + n^2$
Guess: $T(n) = O(n^2)$
Prove: $T(n) \leq cn^2 $
...
1
vote
0answers
22 views
Constant in Substitution method for recurrence
The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS ...
0
votes
1answer
32 views
Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$
Given the condition: $T(O(1)) = O(1)$ and $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $\sqrt{n}$ is not a ...
1
vote
1answer
25 views
Recurrence with a function of n times T()
The master method works well on problems like $T(n)=kT(an)+cn$, but it does not handle problems like
$$T(n)=n^{\frac{1}{3}}T(n^{\frac{2}{3}})+n^2$$
With the number of branches for each partition is a ...
1
vote
1answer
25 views
Using inductive hypothesis on recurrence relation?
I have a recurrence relation as follows
$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$
Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
0
votes
1answer
29 views
Show that the inequality holds for all positive integers
$a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$ for $n>=3$
Show $a_n<3^n$ for all positive integers n
Base case: $a_3 = 2*9+3*2 = 24<=3^3$ is true
Hypothesis: $a_k<=3^k$ for $k\epsilon\mathbb{N}$, ...
1
vote
1answer
33 views
Determining which recursive term is bigger if they share the same definition
We are given a recursive definition:
$a_1 = x,\\a_2=y,
\\a_n= c_1a_{n-1}+c_2a_{n-2} \text{ for }n\ge3 $
where $x,y,c_1,c_2,n$ are natural numbers
we are to prove that $a_n \le c_3^n$ for all n
The ...
1
vote
2answers
82 views
Solving unusual recurrence with two variables
I have the following recurrence relation:
$$T(n,k) = T(n-1,k)+T(n-1,k+1)$$
With the following base cases (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$...
0
votes
1answer
60 views
Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion
We know that the number of permutations possible for $n$ unique items is $n!$.
We can uniquely label each permutation with a number from $0$ to $(n!-1)$.
Suppose if $n=4$, the possible permutations ...
3
votes
1answer
60 views
Recurrence relation for the number of “references” to two mutually recursive function
I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line ...
0
votes
1answer
24 views
Finding the base case for T(n) = T(n - a) + T(a) + cn
I was solving the recurrence using Recursion tree method:
$$ T(n) = T(n - a) + T(a) + cn$$
When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the ...
2
votes
0answers
36 views
trouble solving the recurrence 4T(n/2) + n
I am having trouble figuring out how to solve this recurrence problem...
$$
\begin{aligned}
&4T(n/2) + n \\
= &4(4T(n/4) + n/4) + n \\
= &16T(n/4) + 2n \\
= &4^kT(n/2^k) + kn
\end{...
1
vote
1answer
24 views
For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that ...
1
vote
1answer
20 views
Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution
Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.
(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text ...
0
votes
0answers
19 views
Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)
I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct ...
0
votes
1answer
48 views
How to solve recurrence
I have tried solving it using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact solution.
By substitution I got the following (not ...
0
votes
1answer
39 views
Proving building a balanced BST out of sorted array is $\Theta(n)$
I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$
I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$
I tried to prove it by induction but got stuck ...
1
vote
1answer
60 views
How to solve recursion T(n)=T(n/2)+T(n/3)+n?
How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.
2
votes
1answer
39 views
How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method
Show by induction that any solution to a recurrence of the form
$ T(n) \le 2T(n/3) + c\log_3 n $ is $O(n\log_3 n)$.
Hoping someone can help me with the correct solution. I attempted two ways to ...
1
vote
1answer
26 views
Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms
While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type :
$$\begin{cases}
T(n) = \Theta(1), & \text{for small enough $n$;}\\
T(n) \leq T(a_n n + h(...
1
vote
2answers
42 views
Master Theorem applicable here?
Let
$T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\
1 & \text{if }n=1
\end{cases}$
I need to prove that $t(n) \in ...
1
vote
1answer
39 views
Proving van Emde Boas recurrence
I have tried to solve the following question:
van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$.
...
2
votes
1answer
40 views
Solution of CLRS question 4.6-2
I am trying to solve the 4.6-2 question in CLRS book which is
$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$
While solving the above equation I reach the following point:
$T(n)= n^{\log_ba} + n^{\...
0
votes
0answers
11 views
L-System coordinate conversion (as opposed to drawing): Extending the Hilbert Space Filling Curve
I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
1
vote
1answer
29 views
Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$
The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$
How can I prove by induction that this is $\Omega(n^2)$?
I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$
1
vote
1answer
40 views
Finding a closed formula for recurrence relation
I'm trying to find a closed formula for the below recurrence relation:
For the first one, $n$ is some power of 2
$$T(n) = \begin{cases}
4 & \text{if $n=1$} \\
2T(\frac{n}{2}) +4 & \text{...
0
votes
0answers
18 views
O nation prove with limit theroem? [duplicate]
I'm working on my school homework,even though i found all three of these. It says use limit to compare. I confused , what should i do, i mean its obvious C A B
1
vote
1answer
44 views
Relaxing hypotheses of Master Theorem
This question is related to Master Theorem on oscillating function.
Consider a recurrence of the form
$T(n) = a T(n/b) + f(n)$
Master Theorem's regularity condition excludes some cases (for example,...
0
votes
0answers
64 views
How to solve this recurrence relation using substitution method
Can anyone explain to me how to demonstrate that,
$$T (n, d) ā¤ T (n ā 1, d) + O(d) + d/n (O(dn) + T (n ā 1, d ā 1))$$
is solved by
$$T (n, d) ā¤ bnd!$$
for some constant $b$ using the substitution ...
1
vote
1answer
35 views
Why $T(n)=6T(n-1) + n^3$ has such a mess solution?
I tried to solve the recurrence relation
$T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^...
0
votes
1answer
19 views
How to represent a recurrence that increments by one at each tree level?
I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows:
$$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$
I ...
1
vote
2answers
38 views
Is master theorem applicable for $T(n) = 8T(\frac{n-\sqrt n}4) + n^2$?
Is master theorem applicable for this example?
$$T(n)= 8T \biggl(\frac{n-\sqrt n}4\biggr)+ n^2$$
0
votes
1answer
39 views
Runtime of Divide and Conquer Flavored Bogo Sort
Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively.
https://en....
0
votes
1answer
36 views
How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?
Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.
I am ...
1
vote
1answer
26 views
Calculating complexity for recursive algorithm with codependent relations
I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes:
F(n) = F(n-2) + 2*G(n-1)
G(n) = G(n-2) + F(n-1)
...
0
votes
1answer
125 views
Solving the recurrence of recursive insertion sort
I have solved that the recurrence of running time of the algorithm given as
$$
T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases}
$$
So the ...
0
votes
1answer
58 views
Minimal number of changes to make string into concatenation of $k$ palindromes
The following question is taken from leetcode: 1278. Palindrome Partitioning III
You are given a string $s$ containing lowercase letters and an integer $k$. You need to:
First, change some ...
2
votes
1answer
60 views
Number of parenthesizations and Catalan numbers
I read in CLRS that the number of possible parenthesizations for a product of $n$ matrices is given by the recursive formula:
$$
P(n)=
\begin{cases}
1 & \text{if } n = 1,\\
\sum^{n-1}...
2
votes
1answer
47 views
Recurrence : $T(n) = 4T(n/2) + Ī(n^2/\log n)$
Is there a way to solve this recurrence using master theorem:
$$T(n) = 4T(n/2) + Ī(n^2/\log n)$$
2
votes
1answer
34 views
“Unrolling” a recurrence relation
int function(int n)
{
int i;
if (n <= 0) {
return 0;
} else {
i = random(n - 1);
return function(i) + function(n - 1 - i);
}
}
...
0
votes
0answers
30 views
Asymptotics of reccurence relation
I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$
$T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\
\forall n<10 \quad T(n) = 1$
And if there is such $a$ I need to find the ...
2
votes
1answer
23 views
Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time
The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce ...
1
vote
1answer
14 views
Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?
A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as ...
0
votes
0answers
25 views
Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem
I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
1
vote
2answers
51 views
Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$
Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor
n/8 \rfloor) + n$ is $\in O(n)$.
I will make the bound to be $\in O(cn)$ instead.
Proof by strong induction.
Base case n =1
...
