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
39 views

Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$

I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way: $n = 2^k$ $2^{\frac{2}{k}}\cdot T\left(2^k\right)+\...
2
votes
1answer
1k views

Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ? Thanks!
2
votes
1answer
108 views
+50

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 ...
0
votes
0answers
23 views

Space complexity for divide-and-conquer

Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
0
votes
1answer
34 views

Solving a recurrence relation with two variables

I have this function which traverses each node of a left child-right sibling binary tree once and I want to solve the recurrence relation of the function. First of all I think the relation looks like ...
1
vote
1answer
21 views

Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
0
votes
0answers
23 views

Intuition behind : recursive algorithm takes exponential time [duplicate]

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 ...
0
votes
2answers
45 views

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

I'm trying to bound 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
34 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 ...
1
vote
2answers
45 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
44 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
vote
1answer
43 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
52 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
36 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
48 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
246 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
35 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
48 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
70 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
29 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
52 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
26 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
119 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
33 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
11 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
42 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
86 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
0
votes
0answers
65 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
63 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
64 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
34 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
3answers
105 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
172 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
104 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
57 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
100 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
108 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
71 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
44 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
50 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
182 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
21 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
164 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
66 views
-1
votes
2answers
66 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
141 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
73 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
2 3 4 5
14