# 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
211 views

• 111
1 vote
116 views

• 509
1 vote
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
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
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
776 views

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 ... 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: ... 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? 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 ...
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 ...
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, ...