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
Filter by
Sorted by
Tagged with
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) + \...
user avatar
  • 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) + ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 (...
user avatar
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 ...
user avatar
  • 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_{...
user avatar
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-...
user avatar
  • 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 ...
user avatar
  • 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)$ ...
user avatar
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$. ...
user avatar
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) = ...
user avatar
  • 61
1 vote
0 answers
89 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
user avatar
  • 131
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(\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
  • 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)$, ...
user avatar
  • 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)...
user avatar
  • 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 ...
user avatar
  • 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 \\...
user avatar
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)^{\...
user avatar
  • 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[...
user avatar
  • 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)$
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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(\...
user avatar
  • 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{...
user avatar
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 ...
user avatar
1 vote
0 answers
98 views

Solving complicated recurrence

This question is based on the solution to topcoder SRM-620 question: ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
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: ...
user avatar
  • 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$ ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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}$$ ...
user avatar
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 :
user avatar
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 ...
user avatar
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: ...
user avatar
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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 167