# 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
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)$ ...
37 views

141 views

1 vote
61 views

### Running time of a function $P$ calling itself via $P(P(n/2))$

int P(int n) { if (n==1) return 1; else return P(P(n/2)); } How will this function P(P(n/2)) be executed and what ...
1 vote
81 views

### Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
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: ...
1 vote
53 views

### Tight bound for T(n) = T(n/2) + T($\sqrt{n}$) + n

I have seen examples of how to find the solve the recurrence for T(n) = T($\sqrt{n}$) + n, but how do we go about if there is another T(n/2) in there? So I tried to unfold the recurrence out and this ...
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 ...
130 views

### What is the asymptotic bound for $T(n)= 3T(\sqrt{n})+n^3$?

What is the asymptotic bound? How do you get to the result? $$T(n)= 3 \cdot T(\sqrt{n})+n^3$$
1k views

### Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ? Thanks!
154 views

### Skyline problem with triangular buildings

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites. The following are two variations from the usual Skyline problem: Report ...
Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...