# Questions tagged [recurrence-relation]

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

679 questions
Filter by
Sorted by
Tagged with
19 views

### Prove a Predicate is Primitive Recursive

Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula. Prove ...
27 views

### I need to sort out the theta complexity for lg(n^(1/2))

Can you help me find the theta complexity for lg(n^(1/2))?
35 views

### Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2

I am trying to solve T(n) = 4*T(n/4) + n*[log(n)]^2 I decided to use Master Theorem so I found a,b=4 and logb(a)=1. I thought that 3rd case is the solution but I ...
33 views

### Solving T(n) = 4T(9n/18)+n² [duplicate]

I am trying to solve a recurrence using substitution method. The recurrence relation is: T(n) = 4T(9n/18)+n² How can I find tight asymptotic lower bound (Ω-...
38 views

### Does a closed formula exist for each recurrent formula?

I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the ...
1 vote
54 views

### Formal mathematical resolution for Recurrence Relations

let's suppose we've got a simple Recurrence Relation: $$T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases}$$ At lesson we've resolved it, but I ...
302 views

56 views

### Solving $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ with substitution method

The book I took this example from (Introduction to Algorithms, CLRS) wants to prove that the recurrence relation $$T(n) = 2T(\lfloor n/2 \rfloor)+n$$ is $O(n\lg n)$ using the so-called substitution ...
313 views

### Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
1 vote
46 views

52 views

### Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$

I am trying to solve the recurrence $$T(n) = T(n-1) + (-1)^nn, \quad T(0) = 1.$$ I'm stuck in the summation: \begin{align} T(n) &= T(n-1) + (-1)^n n \\ &= T(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ ...
1 vote
82 views

### What is the Runtime of this recursive algorithm?

I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
888 views

### Solve $T (n) = T (\frac n2) + n(2 - \cos n)$

For the following recurrence relation: $$T (n) = T (n/2) + n(2 - \cos n)$$ I see it based on values of $\cos$ function given that it output values in range, but this does not seem to have anything to ...
35 views

### Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]

How to solve the below relation? $$T(n) = T(0.01n) + T(0.99n) + cn$$ This will not be a balanced tree. For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$. I ...
1 vote
66 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)$ ...
89 views

### Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$

This is not a difficult problem, but I would like please to discuss with you how I solved it: Solving recurrence relation $T(n) = 5T(\frac{n}{3}) + 2n$, $T(1)=2$. What is the value of $T(9)$? This can ...
1 vote
49 views

### $T(n/2 +1)$ substitution in recurrence relation

How to find the recurrence relation using domain range substitution method for the below: $$T(n) = 2T\left(\frac{n}{2} +1\right) + n -2$$ I am unable to get a pattern with this relation as it is ...
1 vote
74 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$. ...
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. ...
133 views

### Recurrence and Time complexity

I am having problem solving this recurrence. Can anyone help me with this please: $$T(n) = 2(T(\sqrt n))^2 , T(1) = 4.$$
1 vote