# Questions tagged [recurrence-relation]

a definition of a sequence where later elements are expressed as a function of earlier elements.

559 questions
Filter by
Sorted by
Tagged with
62 views

### Recurrence $f(n+1)=2f(n)-f(n-1)$ with initial values $f(0)=0,f(1)=1$

How do I solve the following recurrence? $$f(0) = 0, \quad f ((1)) = 1, \quad f((n+1)) = 2*f(n) - f(n-1).$$
45 views

### Solving T(n) = 3T(n/3)+sqrt(n) using master method

I want to know how to find the complexity of this recurrence.
26 views

37 views

I'm trying to solve the recurrence for $T(n) = 7T(n/7) + n$. I know using Master Theorem it's $O(n\log_7n)$, but I want to solve it by substitution method. At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^... 2answers 45 views ### Choosing Constant for Last Step in Substitution METHOD$T(n)= 5T(n/4) + n^2$I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.$T(n)= 5T(n/4) + n^2$Guess:$T(n) = O(n^2)$Prove:$T(n) \leq cn^2 $... 0answers 22 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 ... 1answer 32 views ### Solving recurrence relation$T(n) \leq \sqrt{n}T(\sqrt{n}) + n$Given the condition:$T(O(1)) = O(1)$and$T(n) \leq \sqrt{n}T(\sqrt{n}) + n$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems$\sqrt{n}$is not a ... 1answer 25 views ### Recurrence with a function of n times T() The master method works well on problems like$T(n)=kT(an)+cn$, but it does not handle problems like $$T(n)=n^{\frac{1}{3}}T(n^{\frac{2}{3}})+n^2$$ With the number of branches for each partition is a ... 1answer 25 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 ... 1answer 29 views ### Show that the inequality holds for all positive integers$a_1=2,a_2=9,a_n=2a_{n-1}+3a_{n-2}$for$n>=3$Show$a_n<3^n$for all positive integers n Base case:$a_3 = 2*9+3*2 = 24<=3^3$is true Hypothesis:$a_k<=3^k$for$k\epsilon\mathbb{N}$, ... 1answer 33 views ### Determining which recursive term is bigger if they share the same definition We are given a recursive definition:$a_1 = x,\\a_2=y, \\a_n= c_1a_{n-1}+c_2a_{n-2} \text{ for }n\ge3 $where$x,y,c_1,c_2,n$are natural numbers we are to prove that$a_n \le c_3^n$for all n The ... 2answers 82 views ### Solving unusual recurrence with two variables I have the following recurrence relation: $$T(n,k) = T(n-1,k)+T(n-1,k+1)$$ With the following base cases (for some given constant$C$): For all$x \leq C$and for any$k$:$T(x,k)=1$For all$y \geq C$... 1answer 60 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 ... 1answer 60 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 ... 1answer 24 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 ... 0answers 36 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{... 1answer 24 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 ... 1answer 20 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 ... 0answers 19 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 ... 1answer 48 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 ... 1answer 39 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 ... 1answer 60 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. 1answer 39 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 ... 1answer 26 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 enoughn$;}\\ T(n) \leq T(a_n n + h(... 2answers 42 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 ...
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$. ...