# Questions tagged [recurrence-relation]

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

496 questions
Filter by
Sorted by
Tagged with
22 views

22 views

I was looking at my teacher's notes and came about the following recurrence equation : $$T(n) = \begin{cases} 1 &\quad\text{if } n\leq 1\\ 4T\left(\frac{n}{2}\right) + n^3 ... 2answers 32 views ### Converting a Recurrence Relation to its Closed Form [duplicate] I have a recurrence relation of the form given below (taken from Analysis of Algorithms - An Active Learning Approach by Jeffrey J. McConnell): T(n) = 2T(n - 2) - 15  T(2) = T(1) = 40  I am ... 1answer 86 views ### Akra-Bazzi method integral diverges I want to solve this recursion:$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$My attempt and issue: None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en.... 2answers 40 views ### How do we guess the recurrence relation from the given equation In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is \begin{equation} T(n)=2 T(\lfloor n / 2\... 1answer 96 views ### Upper bound T(n) = 9T(\sqrt{n}) + O(1) The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on$$ T(n) = 9T(\sqrtn) + \Theta(1). $$I am able to get the tree started and find a pattern with the sub-... 1answer 356 views ### Solving recurrence relation with minimum and factorial I need to solve the following recurrence relation, where T(n,m) is defined over \Bbb N_+\times\Bbb N_+. T(n,m)=\begin{cases} 1, & n=1\text{ or }m\leq 2(n-1)!\\ \min\limits_{a,b,c\geq 1,\ c\... 1answer 116 views ### Recurrence with Minimum I need to solve the following recurrece: T(n,m)=\begin{cases} 1, & m\leq 2(n-1)!\\ \min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else} \end{cases} Note:... 1answer 56 views ### solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method How can I solve$$T(n)=T(n-2)+\frac {d}{2}n^2$$I couldnt find d (dont know if I have to) and after 3 iterations I got to k= \frac{n-1}{2} but had trouble to continue. 2answers 51 views ### Number of possible heaps on \{1,…,2^h-1\} Let C_h be the number of possible heaps for the set of keys \{1,...,2^h-1\}. Determine a recurrence relation for C_h via the substitution method and prove it. Definition A binary tree ... 1answer 32 views ### Trouble finding what this recurrence solves to [duplicate] I have a recurrence relation of the form T(n) = 2T(n/2)+O(1) I'm not sure how to deal with the big O-notation in the problem in order to start solving it ? Any help would be appreciated. 1answer 55 views ### What is the closed-form expression for T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1 where T_1 = 1 ? [closed] Problem: Find the closed-form expression for$$ T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1 \tag{1} $$where T_1 = 1 . Calculating this sum I came up with the following result:$$ T_n = 8^{\left(...
Let $G_n$ be defined by $$G_n = \begin{cases} 1 & n=0 \\ 2 & n = 1 \\ 3 & n = 2 \\ 4 & n = 3 \\ 2G_{n-1}-2G_{n-3}+G_{n-4} & n\geq4 \end{cases}$$ How can I prove that $f(n) = n$...