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
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)$ ...
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 $...
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 ...
-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))?
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 ...
-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 (Ω-...
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$. ...
2 votes
2 answers
117 views

simple but (seemingly?) tricky recurrence

I'm cross-posting from math stack exchange after receiving no answers there. I came across the following very simple recurrence-style expression but am having trouble solving it: $$T(2n) \in \theta(T(...
1 vote
1 answer
67 views

Using inductive hypothesis on recurrence relation?

I have a recurrence relation as follows $$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$ Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor ...
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 ...
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 ...
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 ...
1 vote
2 answers
101 views

Which case of the master theorem is this recurrence?

I have a question about the following recurrence relation: $$T(n) = 27 \cdot T\left(\frac n 3\right ) + n^3 \log n$$ Using the master theorem, will this be $T(n) = \Theta(n^3)$, or $T(n) = \Theta(n^3 ...
0 votes
2 answers
70 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}$$ ...
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 $ ...
0 votes
1 answer
44 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: ...
1 vote
1 answer
48 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$. $()((())(...
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 ...
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 ...
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) ...
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 ...
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 ...
1 vote
2 answers
160 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 ...
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)\:+\:...
2 votes
1 answer
141 views

trouble solving the recurrence 4T(n/2) + n

I am having trouble figuring out how to solve this recurrence problem... $$ \begin{aligned} &4T(n/2) + n \\ = &4(4T(n/4) + n/4) + n \\ = &16T(n/4) + 2n \\ = &4^kT(n/2^k) + kn \end{...
0 votes
2 answers
54 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 ...
0 votes
0 answers
40 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 ...
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 ...
1 vote
1 answer
79 views

Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
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 ...
0 votes
2 answers
213 views

Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
1 vote
1 answer
68 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(\...
0 votes
2 answers
844 views

Making a recursive formula for finding amount of ways to spend money on beer

So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this. The information available is that there are $n$ different ...
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 (...
1 vote
1 answer
77 views

Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$. Suppose if $n=4$, the possible permutations ...
0 votes
0 answers
45 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.
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 ...
2 votes
2 answers
249 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
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)+\...
1 vote
2 answers
88 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^{\...
1 vote
1 answer
61 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
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 ...
0 votes
0 answers
27 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: ...
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 ...
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 ...
2 votes
3 answers
130 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$$
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!
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 ...
0 votes
1 answer
673 views

Finding recurrence relations for dynamic programming algorithms

Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...
0 votes
1 answer
57 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
2 3 4 5
14