Questions tagged [recurrence-relation]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
58 views

Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?

In my analysis of algorithms class we were given the following recurrence relation: \begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
1
vote
1answer
53 views

How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$

Consider the following recurrence relationship. \begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\ 2T\left(\...
2
votes
2answers
33 views

How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?

I am interested in the asymptotic bounds of the following recurrence: $$T(n)= T(n - 1) + \frac{1}{n\log n}$$ with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much ...
3
votes
1answer
28 views

Karger's min cut and tips on bounding nonlinear recurrences

I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a ...
0
votes
1answer
35 views

Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

I am doing an exercise which says that this is true: T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$) So I tried to solve it by substitution, but I am getting a non-sense result. So would really ...
1
vote
1answer
37 views

Find the recurrence relation for the following algorithm

The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation. \begin{align} &\text{SORT}(A[0\dots n-1])\colon\\ &\quad \text{...
-1
votes
1answer
30 views

help understanding the recurrence relation of an algorithm

I have the following code which I have to figure out the recurrence relation, but I am having a bit of a trouble understanding what the algorithm does exactly. ...
0
votes
1answer
28 views

How to work out the odd case?

I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to ...
3
votes
1answer
61 views

Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
0
votes
0answers
14 views
1
vote
1answer
30 views

Master theorem: $T(n)=10T(n/9)+n\lg(n)$

I am told to solve the recurrence $$T(n)=10T(n/9)+n\lg(n)$$ using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $...
1
vote
1answer
29 views

Applying Akra–Bazzi with an unbounded number of summands

The Akra–Bazzi method handles recurrences of the form $$ f(n) = \sum_{l=1}^k a_l f(n/b_l). $$ Does it work when then number of $a \cdot f(n/b)$ is not finite, meaning that we have a sum that depends ...
0
votes
2answers
36 views

Solving recurrence $T(n) = T(n - 1) + n$ with substitution method

How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method? I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$: $$T(n) \leq O(n^2) \\ \leq c(n-1)^2+n ...
1
vote
1answer
40 views

Solving the recurrence formula $T(n) = 3T(n/2)+n^2$

What is the solution of the following recurrence? $$ T(n) = 3T(n/2) + n^2, \quad T(1) = 0. $$ I cannot use the master theorem since I need to know the exact final expression, not just it's big O, ...
1
vote
2answers
36 views

Constant terms at each level of a recursion tree

In CLRS, exercise 4.4-5 the following question is asked: Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$ In my recursion tree, the ...
1
vote
2answers
25 views

Big theta notation in substitution proofs for recurrences

Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$. For example, on page 91, the recurrence $$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$ is written like so in ...
1
vote
1answer
39 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
1answer
46 views

Evaluating $T(n)=2^n+4T(\frac{n}{2})$

$$T(n)=2^n+4T(\frac{n}{2})$$ I have started substitution for: $$T(\frac{n}{2})=2^{\frac{n}{2}}+4T(\frac{n}{4})$$ $$T(\frac{n}{4})=2^{\frac{n}{4}}+4T(\frac{n}{8})$$ $$...$$ $$T(\frac{n}{4})=2^n+4[2^{\...
0
votes
1answer
49 views

Recurrence relations and the Master Theorem

Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation: T(n) = 99T(n/100) + log(n!) I'm trying ...
0
votes
1answer
39 views

substitution method on T(n) = T(floor(n/2)) + n recurrence

While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem. Why we assumed that this inequality holds for all ...
1
vote
1answer
22 views

How can recursion tree split a problem into smaller pieces that do not add up?

If I have a recurrence equation: $$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$ It says it splits a problem of size n into 3 subproblems of size n/4. Then it keeps splitting it until the problem size at ...
0
votes
1answer
60 views

Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method

I'm trying to solve this recurrence. I applied the iterative method: $$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{...
1
vote
1answer
47 views

Solving $T(n) = 4T(n/2) + n^3$ with substituton method

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, ...
0
votes
2answers
36 views

Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$

I need to prove that the following recurrence relation is $O(5^n)$: $$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$ And $T(n)=\Theta(1)$ for $n\le 9$. I am trying induction, and proving that there ...
0
votes
1answer
54 views

Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
0
votes
0answers
8 views

What case of the master theorem of this recurrence?

I have a question abou this recurrence: $T(n) = 27T(n/3)+n³/ \log n$ By Master Theorem. will be: $T(n) = \theta(n^3)$ or $T(n) = \theta(n³ \log \log n)$ ?
1
vote
1answer
68 views

Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$

I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$. However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence ...
0
votes
1answer
32 views

Need help with recurrence relation and postcondition of a function

I just wanted to make sure I'm on the right track regarding this. Here's the function that I'm dealing with: ...
0
votes
1answer
28 views

Doing induction on recurrences correctly

I have $$T(n)=T(n-1)+n^{2}$$ And I know, by drawing the recursion tree that this is $\Theta (n^{3})$ However, if I try claiming that it's $O(n^{2})$ through induction: $$T(n)\le c(n-1)^{2}+n^{2}\le cn^...
2
votes
1answer
55 views

Matrix chain multiplication recurrence and its solution

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$. In the classical matrix chain multiplication problem, we wish to minimize the total ...
1
vote
1answer
34 views

What's wrong with this substitution for master's method

I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method: $$T\left(n\right)=T\left(n-1\right)+n^2$$ I did $$S\left(2^n\right)=S\left(2^{n-1}\...
0
votes
0answers
16 views

Write recurrence for cost minimization

So I am trying to find the recurrence for this problem but I feel like it is missing something. An ice cream shop is looking to minimize their operation costs, under the given constraints: They are ...
0
votes
2answers
52 views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$ The base case for $n=1$ seems ...
0
votes
2answers
111 views

Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$

Solve the following recurrence-relations: my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same ...
0
votes
1answer
45 views

Recurrence relations and induction: guessing the right bound

I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$ This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-...
0
votes
2answers
74 views

Failing to solve a recurrence by induction

My question is strongly related to the one asked here: How do I show T(n) = 2T(n-1) + k is O(2^n)? $$T(n)=2T(n-1)+1$$ Going with the steps, I reached the point where: $$c*2^{n}\geq c*2^{n}+1$$ which ...
-2
votes
1answer
104 views

Solving $T(n) = 16T(n/2) + n$

I am trying to solve the following recurrence relation :- $T(n)=16T(n/2)+n$ using masters theorem. I got $\Theta (n^2)$ (Which matched the first case in the theory) which is wrong, any help with this ...
2
votes
1answer
29 views

Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $

$$\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $$ I've found so many similar questions but I couldn't understand any of the answers explanations. When I try to draw a recurrence tree, I see that each '...
1
vote
1answer
45 views

How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$

I try to find tree height such that first i define: $H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$ then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree ...
0
votes
0answers
17 views

Upper bound for reccurence relation with two variables, with linear dependency between them

Given the following reccurence relation: $$T(M,k) = T(M-1,k)+T(M-2,k-1)$$ where $T(0,k)=0, T(1,k)=1, T(M,1)=1$ I have $M^k$ as a general upper bound for $T(M,k)$. Now, suppose I want to give an upper ...
0
votes
1answer
77 views

prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $

i want to prove upper bound of the following recurrence $ T(n) =T(n-\sqrt{n})+1 $ is $ O(\sqrt{n})$.
2
votes
1answer
41 views

Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $

What's the (asymptotic) solution of the following recurrence? $$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$ I tried to solve this with generating functions to find an accurate bound.
0
votes
0answers
45 views

What is the time complexity of this recurrence relation?

T(n) = 12 T(n/(logn)^2) + nlogn How to find the value of b using masters theorem. I think with the help of masters theorem we can't solve this. Is there any other method ?
0
votes
1answer
56 views

Is “backward substitution” and “backtracking” the same thing?

From my limited knowledge, they both are related to solving recurrence relation. Solving recurrence relation using backward substitution Solving recurrence relation using backtracking Can the terms ...
0
votes
0answers
28 views

Solving a recurrence in which $n$ decreases by $\sqrt{2n}$

I'm trying to solve the recurrence $T(n)= 2T(n-\log f(n))+ f(n)$, where $f(n) = 2^{\sqrt{2n}}$, using the master theorem. Which case applies here?
0
votes
1answer
16 views

How do I work out the recurrence relation of the given function?

I am looking to find the recurrence relation (RR) of the fnA(), but I am unsure how $n$ is to be represented. (More specifically, I am trying to work out the ...
1
vote
2answers
78 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). $$
-1
votes
1answer
239 views

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

I want to know how to find the complexity of this recurrence.
0
votes
1answer
44 views

Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$

I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term. We can write $$\frac{T(n)}n=...
1
vote
1answer
47 views

Difficult reccurence with two variables

My question is a follow-up for the following thread: Solving unusual recurrence with two variables I baisically have the same reccurence relation but with a small change--- $$T(n,k) = T(n-1,k)+T(n-m,k+...

1
2 3 4 5
13