# Questions tagged [recurrence-relation]

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

517 questions
Filter by
Sorted by
Tagged with
28 views

### Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$

Is there a way to solve this recurrence using master theorem: $$T(n) = 4T(n/2) + Θ(n^2/\log n)$$
483 views

### Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
22 views

### “Unrolling” a recurrence relation

int function(int n) { int i; if (n <= 0) { return 0; } else { i = random(n - 1); return function(i) + function(n - 1 - i); } } ...
28 views

### Asymptotics of reccurence relation

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 ...
22 views

### Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time

The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce ...
961 views

### DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $max { [v + f(k-1,g-w ), f(k-1,g)] }$ if w <= g and k>0 CCP recurrence relation $min {[1 + f(r,c-v), f(r-1,c)]}$ if v <= c and r>0 I don't ...
12 views

### Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as ...
29 views

### Using Expand, Guess, Verify to solve the following recurrence relation

Hello and thanks to those who bothered reading! I am trying to solve the following recurrence relation, $S(n) = S(n-1) + (2n-1)$, with the following base case: $S(1) = 1$. I already used the ...
47 views

### How can i solve a recursion equation with square root using recursion tree method?

$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$ I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn. I just don't want to ...
37 views

### Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
21 views

### Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

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, ...
49 views

### Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$

Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$. I will make the bound to be $\in O(cn)$ instead. Proof by strong induction. Base case n =1 ...
466 views

### Finding recurrence relation for running time of an algorithm

I am pretty new to this, consider the following algorithm: ...
42 views

### How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I want to solve the following using master theorem. $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$ I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$ I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$ I ...
26 views

### Find the upper bound of the recurrence T(n) = T(n - 4) + n with n is odd

I am trying to solve this recurrence assuming n is odd: $T(n) = T(n - 4) + \Theta n$ What I did so far was: First, $T(n - 4) = T(n - 8) + (n - 4)$, thus we get $T(n) = T(n - 8) + (n - 4) + n$ Next,...
31 views

### Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
112 views

### Not sure if my solution to following recurrence is correct

I have a recurrence relation, it is like the following: $T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm. To solve this and find a $\Theta$ bound, I tried the following:...
402 views

1k views

### Does the master theorem apply to T(n) = 3T(n/3) + nlogn?

I am given an example of a case where the master theorem does not apply, but it seems like it should apply. This was the reasoning: $T(n) = 3T(n/3) + n \log n$ with $a = 3, b=3, f(n) = n\log n$ ...
99 views

### How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$? [duplicate]

The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.
55 views

### Egg dropping problem binomial coefficient recursive solution

I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors) In the binomial coefficient solution we construct a function $f(x,n)$, ...
138 views

### How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n.$$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
### Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?
I am having difficulties in understanding why the recurrence $$T(n)=3T(n/4) + n\log n$$ is solvable with Master Method but $$T(n)=2T(n/2) + n\log n$$ isn't? Despite they both look very similar ...