Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
547
questions
0
votes
1answer
42 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
52 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
21 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
30 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
22 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
15 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
18 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 ...
1
vote
1answer
33 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
37 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 ...
-4
votes
0answers
16 views
closed form for the following recurrence relation
$t(k,m,n) = \frac{m}{k}t(k-1,m-1,n-1)+ \frac{k-m}{k} t(k-2,m-1,n-1) + \frac{k-m}{k} $ , where $k \geq m \geq n$
1
vote
1answer
41 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
38 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
22 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
38 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
29 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$.
...
1
vote
1answer
38 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
9 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
26 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
39 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
35 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
34 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
18 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
37 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
38 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
31 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
25 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
63 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
43 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
44 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}...
1
vote
1answer
42 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
27 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
13 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
22 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
50 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
...
1
vote
0answers
45 views
How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$
I want to solve the following using master theorem.
$T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$
I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$
I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$
I ...
1
vote
0answers
26 views
Find the upper bound of the recurrence T(n) = T(n - 4) + n with n is odd
I am trying to solve this recurrence assuming n is odd:
$T(n) = T(n - 4) + \Theta n$
What I did so far was:
First, $T(n - 4) = T(n - 8) + (n - 4) $, thus we get $T(n) = T(n - 8) + (n - 4) + n$
Next,...
2
votes
1answer
32 views
Recurrence Relations
I am starting to learn recurrence relations in class and I am having issue with this example:
T(N) = 2N - 1 + T(N-1)
I am bit confused as to get the base case.
I'm sorry if this seems elementary, ...
0
votes
1answer
23 views
Converting a function with single parameter to a function with multiple parameters
I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:
Given a string or a list, do an aggregation operation on each of its elements. Here ...
0
votes
1answer
61 views
How can i solve a recursion equation with square root using recursion tree method?
$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$
I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.
I just don't want to ...
0
votes
1answer
37 views
Solving a peculiar recurence relation
Given recurrence:
$T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$
The way I solved is like this (using change of variables method, as mentioned in CLRS):
Let $n = 2^k$
$T(...
0
votes
2answers
51 views
Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi
We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work.
...
2
votes
2answers
90 views
Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)
Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
3
votes
1answer
72 views
Closed formula for two variable recurrence
I would like to know if there exists a closed form formula to the following recurrence:
$f(s, 0) = 1$
$f(s,b) = \displaystyle\sum_{i=1}^{min(s, b)} \left[
(s-i+1)\times f(i, b-i) \right] $
This ...
1
vote
1answer
43 views
Solving a recurrence relation with T(n) = 2 * T(n/3) + 5n [duplicate]
I have no idea how to solve this one - I end up with $\sum_{i=0}^k (2^k * 5 * 3^i)$ but I have no clue how to get any further than that (e.g. resolve the sum even further, if it's even correct to ...
1
vote
1answer
150 views
Recurrence relation and time complexity of recursive factorial
I'm trying to find out time complexity of a recursive factorial algorithm which canĀ be written as:
Ā
fact(n)
{
Ā if(n == 1)
Ā return 1;
Ā else
Ā return n*fact(n-1)
Ā }
...
2
votes
2answers
58 views
Summing $1,3,5,\ldots$
I solved a recurrence to get the formula $T(n) = \sum_{i=1}^{k}2i+1$ for $k = \frac{n-1}{2}$, namely
$$ T(n) = 1 + 3 + \dots + (n-4) + (n-2) + n, $$
but I'm not sure how to finish off the problem by ...
