Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
536
questions
2
votes
1answer
24 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
34 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
21 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
37 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
25 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
38 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
17 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
30 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
62 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
16 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
36 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
27 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
52 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
40 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
41 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
39 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
24 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
22 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
51 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
36 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
1answer
42 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
81 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
71 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
41 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
128 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 ...
3
votes
2answers
165 views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
3
votes
1answer
128 views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
1
vote
0answers
61 views
Egg dropping problem binomial coefficient recursive solution
I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)
In the binomial coefficient solution we construct a function $f(x,n)$, ...
2
votes
1answer
188 views
How to solve $T(n)= 4T(\sqrt n) +\log^2n$?
Consider the recurrence
$$T(n)= 4T(\sqrt n) + \log^2n. $$
I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
1
vote
1answer
50 views
Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?
I am having difficulties in understanding why the recurrence
$$T(n)=3T(n/4) + n\log n$$
is solvable with Master Method but
$$T(n)=2T(n/2) + n\log n$$
isn't?
Despite they both look very similar ...
1
vote
0answers
29 views
Finding the closed form of this recurrence
We have the following recurrence $T$:
$$
T(n,k) = \left\{
\begin{array}{ll}
\alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\
T(\lceil n / 2 \rceil, k)...
1
vote
0answers
33 views
Hanoi towers recursive expression for EVERY algorithm
What the recursive algorithm for moving $n$ disks says, is:
If $n > 1$, move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n > 1$, move $n-1$ discs from B to C.
Let $T_n$ be ...
0
votes
0answers
75 views
Induction proof given recurrence of algorithm
I am having trouble starting this proof and wanted some clarification. Here are the details given:
...
0
votes
0answers
47 views
Time Complexity calculation using recursion tree method
What is the time complexity of the following recurrence equation :
T(n) = T(n/2) + T(n/4) + T(n/8) + n
I solved it using recursion tree method and I'm getting O(n) as the answer.
Please let me know ...
1
vote
1answer
22 views
Why can we ignore the constant factor in Weis's proof of the Master Theorem
In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem. This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ... I don't understand ...
1
vote
0answers
60 views
How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?
I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$.
$V(j, k) = \begin{cases} tj & k \leq 2 \\...
