Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
66
questions with no upvoted or accepted answers
6
votes
0
answers
211
views
Are there master theorems that deal with parameters of the form $n-c$?
While thinking about this question on a recurrence I checked out some stronger master theorems.
Unfortunately, they do not seem to apply because terms
$\qquad\displaystyle T(n) = \dots + T(n-1) + \...
- 70.8k
3
votes
0
answers
52
views
Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm
I have a graph algorithm that runs in:
$$ T(n, m) = \begin{cases}
c_1 & n \leq 2 \lor m = 1\\
T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + ...
- 4,361
2
votes
0
answers
64
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 ...
- 141
2
votes
0
answers
27
views
Useful conditions for proving super polynomial lower bound for some kind of recurrences
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$
Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
- 151
2
votes
0
answers
492
views
Analysis expected depth of a binary search tree given random values?
I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
- 653
2
votes
0
answers
91
views
Solving the following recurrence relation derived from a Markov chain
I have the following system of recursive relations on $y_{i,j}$ that are derived from a Markov chain and that I am having difficulty in solving. For $i\ge 1$ and $j \ge 1$, we have
$$y_{i,j} \times (...
- 121
2
votes
0
answers
98
views
Counting inversions with index constraint
I have a series of line segments $l_i=(a_i,b_i)$ with $i=1,2,3...n$
$a_i$ and $b_i$ are their starting and ending points coordinates in $x$ axis.
The question is how to find a algorithm that is ...
- 121
2
votes
1
answer
796
views
Solving T(n) = 2T(n/3) + 2 T(2n/3) + n
The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:
Recursion tree. We see that
$$\begin{align}
\sum_{...
- 204
2
votes
1
answer
54
views
Counting permutations whose elements are not exactly their index ± 1
This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M
The $M=0$ case has already been solved, but no one was sure how to work out the non-...
- 317
1
vote
1
answer
49
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
1
answer
61
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
1
vote
1
answer
69
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
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
1
vote
0
answers
89
views
1
vote
1
answer
68
views
How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$
Consider the following recurrence relationship.
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
2T\left(\...
- 157
1
vote
0
answers
53
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 ...
- 13
1
vote
1
answer
63
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 ...
- 11
1
vote
1
answer
77
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 ...
- 11
1
vote
0
answers
200
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 ...
- 167
1
vote
0
answers
28
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,...
- 11
1
vote
0
answers
138
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)$, ...
- 133
1
vote
0
answers
40
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)...
- 11
1
vote
0
answers
42
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 ...
- 133
1
vote
0
answers
188
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 \\...
- 111
1
vote
0
answers
116
views
What are the asymptotic bounds (upper bound on time complexity) of the following function?
I am trying to find the upper bound on time complexity of the recursive function defined by the following equation:
$$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
- 11
1
vote
0
answers
53
views
Recurrence Relation for Column Major Form of multidimensional array
A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[...
- 509
1
vote
0
answers
86
views
Question on Recurrence $T^2(n) = T(n/2) * T(2n) - T(n) * T(n/2)$
Need help solving this recurrence:
$T^2(n) = T(n/2) * T(2n) - T(n) * T(n/2)$
- 11
1
vote
0
answers
38
views
Applications of the (cumulated) ruler function in algorithm analysis
In Chapter 2 (Page 76) of the book "An Introduction to the Analysis of Algorithms (2nd edition)" by Robert Sedgewick and Philippe Flajolet, the authors introduce two functions:
Definition Given an ...
- 9,179
1
vote
0
answers
916
views
Help with deterministic selection algorithm
All we know what is Deterministic Selection Algorithm:
Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
1
vote
0
answers
776
views
Why do we count the ceils and floors in recursive functions?
When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of
$$
T(n) = T(\...
- 1,357
1
vote
0
answers
53
views
Understanding exponential computation by digit recurrence
I've met in a book the following algorithm that computes the exponential:
Input: $t, n$ ($n$ is the number of steps)
Output: $E_n$
$\begin{array}{l}
\mbox{define $t_0 = 0$ ; $E_0 = 1$} \\
\mbox{...
- 653
1
vote
0
answers
79
views
Dynamic Programming - Seemingly unnecessary recursion?
I am working on my thesis on revenue management. I have been over the following problem multiple times now, but I fail to see where my mistake is. This example is based on The Theory and Practice of ...
- 19
1
vote
0
answers
98
views
Solving complicated recurrence
This question is based on the solution to topcoder SRM-620 question:
...
- 159
0
votes
0
answers
35
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
0
votes
0
answers
45
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.
0
votes
0
answers
27
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
0
votes
0
answers
86
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
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.
...
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
0
votes
0
answers
54
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
$...
- 377
0
votes
0
answers
23
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
0
answers
88
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 ...
- 123
0
votes
2
answers
69
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}$$
...
- 11
0
votes
0
answers
22
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 :
0
votes
0
answers
67
views
Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$
Lets define function $T(n)$ as
\begin{align*}
T(1) &= T(2) = 1\\
T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\
\end{align*}
Does $T(n)=O(\log(n))$? I have no idea how to ...
0
votes
1
answer
43
views
Need help with recurrence relation and postcondition of a function
I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
...
0
votes
0
answers
38
views
Solving a recurrence in which $n$ decreases by $\sqrt{2n}$
I'm trying to solve the recurrence
$T(n)= 2T(n-\log f(n))+ f(n)$, where $f(n) = 2^{\sqrt{2n}}$,
using the master theorem. Which case applies here?
- 111
0
votes
0
answers
71
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
0
votes
0
answers
31
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 ...
- 153
0
votes
0
answers
58
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, ...
- 167