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

Prove a Predicate is Primitive Recursive

Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula. Prove ...
user avatar
-2 votes
2 answers
27 views

I need to sort out the theta complexity for lg(n^(1/2))

Can you help me find the theta complexity for lg(n^(1/2))?
user avatar
0 votes
1 answer
35 views

Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2

I am trying to solve T(n) = 4*T(n/4) + n*[log(n)]^2 I decided to use Master Theorem so I found a,b=4 and logb(a)=1. I thought that 3rd case is the solution but I ...
user avatar
-3 votes
0 answers
33 views

Solving T(n) = 4T(9n/18)+n² [duplicate]

I am trying to solve a recurrence using substitution method. The recurrence relation is: T(n) = 4T(9n/18)+n² How can I find tight asymptotic lower bound (Ω-...
user avatar
0 votes
1 answer
38 views

Does a closed formula exist for each recurrent formula?

I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the ...
user avatar
1 vote
2 answers
54 views

Formal mathematical resolution for Recurrence Relations

let's suppose we've got a simple Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases} $$ At lesson we've resolved it, but I ...
user avatar
3 votes
2 answers
302 views

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

Given the algorithm MYSTERY-ALG(n >= 0) 1 if n < 3 then 2 return 1 3 else 4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1) I defined a recurrence $ ...
user avatar
  • 45
1 vote
1 answer
49 views

A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$

Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$. That is, $(())$ has $n = 4, d = 2$. $()((())(...
user avatar
2 votes
2 answers
56 views

Solving $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ with substitution method

The book I took this example from (Introduction to Algorithms, CLRS) wants to prove that the recurrence relation $$T(n) = 2T(\lfloor n/2 \rfloor)+n$$ is $O(n\lg n)$ using the so-called substitution ...
user avatar
3 votes
2 answers
313 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
user avatar
  • 337
1 vote
1 answer
46 views

Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence: $$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$ Later, they write the same recurrence as $$T(n) ...
user avatar
0 votes
1 answer
37 views

Recursive function - proof by induction

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists. I've encountered the following function: $f([])=[]$ (empty list) $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ and $...
user avatar
  • 1
2 votes
1 answer
56 views

Trying to understand the basic about recurrence trees

I have little background on recurrence trees, and I am working on the following exercise: Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
user avatar
  • 187
0 votes
0 answers
41 views

Optimal substructure

Is optimal substructure lost when there are different functions in the recurrence relation? Does optimal substructure require the construction of its solution only from subproblems of the same ...
user avatar
  • 145
1 vote
1 answer
36 views

Find the proper hypothesis for the substitution method for a recurrence problem

I'm trying to solve a recurrence problem using substitution method: Given the following recurrence equation: $ T(n) = \begin{cases} 3 &n = 0 \\ 3T(\frac{n}{5}) + T(\frac{n}{6}) + n&n ...
user avatar
0 votes
0 answers
46 views

Solving recurrence finding theta of T(n)=T(log n)+1

$$ T(n)=T(\log n)+1 $$ $$ T(n)=\Theta(...) $$ I want to find theta of $T(n)$. I tried the master theorem but failed.
user avatar
2 votes
2 answers
42 views

Programmatically determine if a tie is possible in US elections

Problem 3.5 from book: "Algorithms for interviews". There are 51 states (+ Washington DC), each with different amount of votes. Find the number of votes of each state here Suppose there are ...
user avatar
  • 123
1 vote
1 answer
80 views

Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
user avatar
  • 11
1 vote
3 answers
95 views

Solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$

I am trying to solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$ I tried method I saw but I do not fully understand which looks like: $T\left(n-1\right)\:=\:3T\left(n-2\right)\:+\:...
user avatar
1 vote
1 answer
81 views

Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
user avatar
  • 45
1 vote
3 answers
52 views

Solve $T(n) = \frac78T(\frac78n) + \frac78n$

The recurrent function $T(n) = \frac78T\left(\frac78n\right)+\frac78n$ where $T(1) = 0$ and $n = \left(\frac87\right)^k$ represents the running time of an algorithm. How can I find a more simple form (...
user avatar
  • 11
0 votes
0 answers
28 views

Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?

I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks. He said: ...
user avatar
  • 1
1 vote
2 answers
53 views

Tight bound for T(n) = T(n/2) + T($\sqrt{n}$) + n

I have seen examples of how to find the solve the recurrence for T(n) = T($\sqrt{n}$) + n, but how do we go about if there is another T(n/2) in there? So I tried to unfold the recurrence out and this ...
user avatar
  • 21
0 votes
3 answers
60 views

Recurrence relation with O(loglogn)

I am trying to solve a recurrence relationship as follows: T(n)=T(n^1/2)+O(loglogn) I can solve the T(n^1/2) part quite easily, but I am completely lost as to what to do with an O(loglogn). I cant use ...
user avatar
1 vote
2 answers
93 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)+\...
user avatar
2 votes
1 answer
1k views

Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ? Thanks!
user avatar
  • 29
3 votes
1 answer
154 views

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 ...
user avatar
0 votes
0 answers
97 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$ ...
user avatar
  • 101
0 votes
1 answer
58 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 ...
user avatar
1 vote
1 answer
29 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: ...
user avatar
  • 123
0 votes
0 answers
24 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 ...
user avatar
0 votes
2 answers
103 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?
user avatar
1 vote
1 answer
128 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 ...
user avatar
1 vote
2 answers
55 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 ...
user avatar
  • 11
2 votes
3 answers
75 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 ...
user avatar
1 vote
1 answer
191 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 ...
user avatar
0 votes
1 answer
76 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)$?
user avatar
0 votes
1 answer
47 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 ...
user avatar
  • 459
3 votes
1 answer
52 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 \\ ...
user avatar
1 vote
1 answer
82 views

What is the Runtime of this recursive algorithm?

I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
user avatar
3 votes
3 answers
888 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 ...
user avatar
  • 459
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
66 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)$ ...
user avatar
0 votes
2 answers
89 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 ...
user avatar
  • 459
1 vote
2 answers
49 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 ...
user avatar
  • 35
1 vote
1 answer
74 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$. ...
user avatar
0 votes
0 answers
33 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. ...
user avatar
3 votes
2 answers
133 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. $$
user avatar
1 vote
0 answers
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) = ...
user avatar
  • 61
0 votes
0 answers
14 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 ...
user avatar

1
2 3 4 5
14