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
0
votes
1answer
28 views

Iteration Vs Induction Method

I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit ...
3
votes
1answer
28 views

Approximation of rational sequences via linear recurrences of small order

I wish to approximate a sequence of rational numbers using a linear recurrence of order $k$ for some small $k$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact ...
0
votes
1answer
46 views

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

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

How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

Can somebody help me with this recurrence please? $T(n)=4T(\sqrt{n}/3)+(\log n)^2$
-2
votes
0answers
91 views

Find the number of additions in a recursive relation of two variables

Consider following recursive relations: $$ F(i,0)=\begin{cases} F(i+1,0) + F(i+1,1) & \text{ if } i<n,\\ 0 &\text{otherwise}\\ \end{cases}$$ $$ F(i,1)=\begin{cases} 2F(i+1,0) + F(i+...
1
vote
1answer
25 views

Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$

What is the asymptotic rate of growth of the following recurrence relation? $$ f(x) = \begin{cases} 8f(x/2) + Θ(1) & \text{ if } x^2 > M, \\ M & \text{ if } x^2 \leq M. \end{cases} $$ Here ...
2
votes
0answers
44 views

Two dimensional recursive function in $O(\log n)$ time complexity

It is well known that a recursive sequence or $1$-d sequence can be calculated in $O( \log n)$ time given that it has the form $$a_n=\sum_{k=1}^{n} C_ka_{n-k},$$ where $C_k$ is a constant. Examples ...
1
vote
1answer
33 views

How to solve recurrence of a binary tree

I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it. This function calculates both the height and if its a balanced tree. ...
1
vote
2answers
62 views

Solving constants in the recursive term with master theorem

We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the ...
1
vote
1answer
62 views

Recurrence $T(n) = T(n - \log n) + 1$

Given recurrence relation : $$ T(n) = \begin{cases} T(n-\log n) + 1 & \text{if } n \ge 1, \\ 1 & \text{otherwise.}\\ \end{cases} $$ To find asymptotic order of $T(n)$ i do as follow:...
-1
votes
1answer
40 views

Time complexity a recursive function [duplicate]

Suppose given recurrence relation $$T(n)=T(\sqrt{n})+T(n-\sqrt{n})+n$$ $$T(1)=O(1)$$ How we can find an order of above recurrence relation? My attempt: I read following post, but get stuck in ...
0
votes
1answer
32 views

Divide and conquer recurrence relation

I have divide and conquer problem and below is the recurrence relation for it $$\begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\ t(n) &= a\cdot t (n/4) + O(n^2) \end{align}$$ ...
0
votes
1answer
50 views

How to calculate the average depth of a binary tree?

My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach ...
0
votes
0answers
19 views

Recurrence relation of an algorithm

how can I know what are the recursive calls of this algorithm ? in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation. Here is the algorithm :
2
votes
2answers
134 views

Asymptotic order of a recursive function

\begin{gather*} T(n)=T(\frac{n}{\log n})+O(1) \end{gather*} \begin{gather*} T(1)=O(1) \end{gather*} I try to use substitution method to solve $T(n)$, but because of $\log n$ get stuck. Can we use ...
1
vote
2answers
40 views
-1
votes
2answers
51 views

Accurate height of recursion tree for given recursion

We are trying to find height of following recursion formula in terms of $n,k$: \begin{gather*} T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk \end{gather*} \begin{gather*} T(n,1)=T(1,k)=O(1) \end{...
0
votes
3answers
88 views

Solving a recurrence of uneven subproblems without Akra-Bazzi

I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$ I observed it ...
1
vote
1answer
60 views

Solving recurrence relation for running time of combination formula

I'm trying to solve the following Time complexity recurrence relation: $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$ that come from following code: ...
1
vote
1answer
38 views

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem

Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$ My approach with recurrence tree: $n \sim n\log(n)$ $\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$ $\frac{n}{4} \...
2
votes
1answer
35 views

Showing asymptotic lower bound on log of recurrence

I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows: $T(1) ...
1
vote
1answer
19 views

Which of the following is a more appropriate complexity for this reccursive function?

Given the following recurrence relation: \begin{gather*} h(A) = \begin{cases} 0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\ 1+h(A-1),\text{ }\text{ }A\text{ is odd} \\ 1+h(\frac{A}{2}),\...
1
vote
1answer
24 views

On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$

Consider the recurrence $$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$ What is the condition on $a,b$ that guarantees $T(n)=O(n^c)$? With substitution I get $$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})...
0
votes
0answers
19 views

Computer Science [duplicate]

I am trying to solve the following problem to find big-theta. I am having a lot of trouble, if anyone can help! T(n)=8T(√n)+log^2(e^n)? The logarithm is base 2 and is squared.
0
votes
0answers
44 views

Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$

Lets define function $T(n)$ as \begin{align*} T(1) &= T(2) = 1\\ T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\ \end{align*} Does $T(n)=O(\log(n))$? I have no idea how to ...
2
votes
2answers
44 views

How to solve recursion T(n) = T(n/3) + T(2n/3) + n?

$T(n) = T(n/3) + T(2n/3) + n$ How can I solve this recurrence formula?
-2
votes
2answers
44 views

Solve T(1) = 1 T(n) = T(n-1) + n^2 for n ≥ 2

I am not able to solve the following recurrence relation: $$ T(n) = \begin{cases} T(n-1) + n^2 & \text{if } n \ge 2, \\ 1 & \text{otherwise.}\\ \end{cases} $$ How do I start?
0
votes
0answers
16 views

Starter book on solving recurrences

I am having problems with algorithms, particularly solving them using recurrence. can anyone suggest an easy to understand basics introduction to this so that I can get my head around the concept.
1
vote
2answers
64 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
60 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
38 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
36 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
41 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
50 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
31 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
35 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
63 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
2
votes
1answer
39 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
31 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
312 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
152 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
44 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
43 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
47 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
50 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
46 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
116 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
2 3 4 5
13