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
0answers
17 views

Intuition behind : recursive algorithm takes exponential time

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
-3
votes
0answers
10 views

recurrence equation 2T(n-4) + n^2 solution?

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
0
votes
2answers
30 views

How to solve $T(n) = T(27n/9) + n^3$ with substitution method

I'm trying to solve this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?
1
vote
1answer
23 views

Finding time complexity $T(n) = 2^n T(n/2) + n^n$

I am applying substitution method to find the time complexity of the following recurrence relation. But I am having difficulty solving it past a certain point. $$T(n) = 2^n T(n/2) + n^n$$ After ...
0
votes
2answers
34 views

Regularity condition for cases 1 & 2

My question concerns the version of the Master Theorem described in CLRS and in this handout. I already understand the following: If the regularity condition in case 3 does not hold, then we can't ...
1
vote
1answer
31 views

Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
-1
votes
0answers
22 views

How to solve the recurrence relation T(n) = T(n/2) + n^2 using recursion trees?

I drew the recursion tree but I can't seem to make a conclusion as to what the total amount of work done is.
1
vote
1answer
24 views

Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
0
votes
1answer
40 views

How to solve $T(n) = 2T(n/4) + n \log n$ with substitution method?

I am trying to solve this recurrence with substitution method. I guess $T(n) = \Theta(n \log n)$ (with Master Theoreme). Can someone show me how to demonstrate the upper bound $T(n) = O(n \log n)$?
0
votes
1answer
34 views

Solve $T(n) = 3T(\frac n3 + 5) +\frac n2$

Given recursive equation, $T(n) = 3T(\frac n3 + 5) +\frac n2$ $$ \begin{align} T(n) = 3T(\frac n3 + 5) +\frac n2 \tag{1} \label{1} \\ \lt 3T(n- 15) +\frac n2\\ \lt 3 \left(3T\left(\frac{(n- 15)}{3} +5 ...
3
votes
1answer
47 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 \\ ...
3
votes
3answers
198 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 ...
0
votes
0answers
34 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
1answer
46 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)$ ...
0
votes
2answers
58 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
1answer
26 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
1answer
50 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$. ...
0
votes
0answers
23 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. ...
3
votes
2answers
102 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
0answers
31 views

Is there a class of recurrence relations that can't be solved using the substitution method?

Is there a class of recurrence relations that can't be solved using the substitution method? Let me explain the motivation behind this question by an example. Consider the recurrence relation $T(n) = ...
0
votes
0answers
10 views

Video lectures showing the way to solve recurrence relations using Akra-Bazzi method, taking ample examples

After reading about the Akra-Bazzi method of solving recurrence relations from the chapter notes of the CLRS text (p. 112-113 of [3e]), I felt that the method is a bit subtle. Even the authors say ...
0
votes
0answers
52 views

Merging the submatrices' time complexity in matrix multiplication

This is a problem of CLRS: What is the largest $k$ such that if you can multiply $3 \times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply $...
0
votes
2answers
34 views

recurrence with exponentials

I am trying to figure out on how to approach the problem on finding proving the asymptotic of an exponential recurrence. It is described as such: t(n)=4t(n/2)+2^n with t(1)=1 for n>=5 From what I ...
0
votes
0answers
16 views

What is the return value of the following code R(n) = 2R(√n) + n?

Algorithm rec(n) { if (n ≤ 2) return 1 else { return (2*rec(√n) + n) } } Return value recurrence relation, I want to find the exact value and not ...
0
votes
1answer
74 views

Multiplying two integers by dividing each into 3 parts

Integer Multiplication: $x$ and $y$ are two n-bit integers, where $n=3^k$ for some $k>0$. We break $x$ into three parts $a$, $b$, $c$, each with $n/3$ bits; and $y$ into three parts $d$, $e$, $f$, ...
1
vote
0answers
85 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
0
votes
0answers
59 views

Total work done at a recursion tree level

In the proof of Master theorem in Dasgupta's Algorithms the author says that the total work done at a recursion tree level is $$a^k \times O\left(\frac{n}{b^k}\right)^d$$ where $a$ is the branching ...
1
vote
1answer
51 views

Solving $T(n) = 2T(n/2) + \log n$ using the master theorem

Is there a substitution, so that the following recurrence relation can be solved using the given version of the master theorem? $$ T(n) = 2T(n/2) + \log n $$ Let $a,b \in \mathbb{N}$, where $b > 1$...
2
votes
1answer
60 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
32 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 ...
2
votes
2answers
91 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
3answers
136 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
2answers
103 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
53 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
70 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
97 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
70 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
42 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
46 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
157 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
20 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
159 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
54 views
-1
votes
2answers
63 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
126 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
70 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
2answers
82 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
2answers
54 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
20 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
29 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})...

1
2 3 4 5
14