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
1 answer
32 views

Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
patayala's user avatar
1 vote
2 answers
59 views

Solve the recurrence $T(n)=T(n-2)+\frac{1}{\lg{n}}$

Assume this recurrence: $$T(n)=T(n-2)+\frac{1}{\lg{n}}$$ I tried to draw its recurrence tree and I reached that the whole cost is $\dfrac{1}{\lg{n}}+\dfrac{1}{\lg{n-2}}+\dots+\dfrac{1}{x}$ that $x$ is ...
Mason Rashford's user avatar
1 vote
1 answer
29 views

Solve the recurrence $T(n)=T(n-1)+\frac{1}{n}$

Assume this recurrence: $$T(n)=T(n-1)+\frac{1}{n}$$ As we can use Master Theorem and Akra-Bazzi method here, I tried to draw a recurrence tree and I reached the whole cost of this tree is $\frac{1}{1}+...
Ilkay Burak's user avatar
1 vote
1 answer
31 views

Can this reccurrence recurrence be solved using Master Theorem?

Assume we have: $$T(n)=7T(\frac{n}{2})+n^2\lg{n}$$ Can we solve it using master theorem? As we know $n^{\lg_2{7}}\approx n^{2.81}$. On the other hand, we have $f(n)=n^2\lg n$. So we should compare $n^....
Ilkay Burak's user avatar
1 vote
1 answer
30 views

Solve a recurrence using Akra-Bazzi method where $p$ is not integer and integration is not easy

I recently faced this problem in CLRS ed.4 and couldn't find out how to attack it and solve it. Here's the recurrence: $$T(n)=3T(\frac{n}{3})+8T(\frac{n}{4})+\frac{n^2}{\log{n}}$$ Here's what I tried: ...
Mason Rashford's user avatar
0 votes
1 answer
37 views

Solving Recurrence Relations with induction

We got the following tasks in our Higher Algorithm class, to repeat our proof techniques from class: Find asymptotic upper bounds (as sharp as possible) for $T(n)$ in each of the following cases, ...
petrit.vidishiqi's user avatar
0 votes
1 answer
57 views

solve $T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$ using Akra-Bazzi method

Assume we have this recurrence: $$T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$$ We want to solve it using Akra-Bazzi method. As we know, $\sum_{i=1}^k\dfrac{a_i}{...
Mason Rashford's user avatar
3 votes
1 answer
91 views

On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty

On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from ...
John's user avatar
  • 31
0 votes
1 answer
33 views

Struggling with Recurrence Relation using Telescoping Approach

I have the following recurrence relation that I am trying to solve using the telescoping approach: $T(n) = \begin{cases} T(\frac{n}{4})+ n^2 & \text{for } n \geq 4 \\ 1 & \text{otherwise} \...
Nancy Drake's user avatar
0 votes
2 answers
45 views

Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Please first take a brief look at my previous question. Here I want to do something similar but for $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$. I know the answer is $T(n)=\Theta(n\log^2{n})$ and I want ...
Mason Rashford's user avatar
0 votes
1 answer
34 views

find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$

We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$. There's something that confuses me. We ...
Mason Rashford's user avatar
0 votes
1 answer
55 views

Find time complexity of $T(n)=3T(n-2)+O(n)$

I try to find the time complexity of following recurrence relation: $$T(n) = 3T(n-2) + O(n)$$ After subtitution,I get: $$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$ I wonder if the ...
Ash丶Dr's user avatar
1 vote
2 answers
146 views

Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

We have this recurrence: $$T(n)=10T(\frac{n}{3})+n\sqrt{n}.$$ We can solve it using Master Theorem and say it is $\Theta(n^{\log_3{10}})$. I want to prove it using induction but I don't know the ...
Mason Rashford's user avatar
0 votes
0 answers
40 views

Is my mathematical representation of search in binary search tree correct?

You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node's value equals <...
ilovewt's user avatar
  • 113
-1 votes
1 answer
45 views

Solve Recurrence Equation: 𝑇(𝑛)=𝑇(𝑛−4)+𝑛^2

I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method. I was wondering if what I write below was correct and obviously the result: $T(n) = n^2 + T(n-4) =...
emacos's user avatar
  • 121
0 votes
1 answer
59 views

Substitution method for the upper bound of a recurrence without an explicit base case

Pages 90-91 of 'Introduction to Algorithms' (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence: $$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{...
user51462's user avatar
  • 123
2 votes
2 answers
67 views

Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The fourth edition of 'Introduction to Algorithms' defines algorithmic recurrences on page 77 as follows: **Algorithmic recurrences [...] A recurrence is algorithmic, if for every sufficiently large ...
user51462's user avatar
  • 123
0 votes
2 answers
53 views

Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added): 2.3.2 Analyzing divide-and-conquer algorithms [...] A recurrence for the running time of a ...
user51462's user avatar
  • 123
0 votes
0 answers
42 views

The master theorem soution to T(n) : T(n/4) + logn

When i tried to find the time complexity of this recurrence relation with the master theorem, I got log^2n, but I'm told that it's logn. I used the masters theorem, for this case.. a=b^k (1=4^0) ... ...
Yor's user avatar
  • 1
0 votes
1 answer
63 views

Comparisons using Quicksort with the median as the pivot

Background Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm: Quicksort($a$): (1) If length($a$) $...
FD_bfa's user avatar
  • 103
0 votes
1 answer
67 views

How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c

I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m). The base ...
Samiddha 's user avatar
0 votes
0 answers
382 views

How to generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices?

the question is as follows: "Generalize MATRIX-MULTIPLY-RECURSIVE to multiply n × n matrices for which n is not necessarily an exact power of 2. Give a recurrence describing its running time. ...
Portgas D Ace's user avatar
0 votes
1 answer
87 views

What recurrence describes the time complexity of this algorithm?

The problem is as follows: The input is an array $A$ of $n$ natural numbers such that: (1) if the maximum occurs in $A[p]$ for an index $p$, then $$A[1] \leq \ldots \leq A[p-1] \leq A[p]$$ and $$A[p] ...
Lucas Peres's user avatar
0 votes
0 answers
26 views

Does a bijective function exists behind every recurrence relation?

Consider these 2 questions where recurrence relations can be applied: Q1) Given an (nxm) where n denotes rows and m denotes columns of a grid, find the number of unique paths ($a_{n,m}$) that goes ...
rustlecho's user avatar
0 votes
0 answers
155 views

Recurrence relation for TSP using recursion

This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph: ...
Hackerman's user avatar
  • 101
0 votes
5 answers
149 views

Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$

I've tried to expand the recursion: $$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$ We have a total of $...
Yoxbox's user avatar
  • 3
2 votes
0 answers
75 views

Recurrence Relation for Longest Increasing Subsequence Problem

I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
Sabe's user avatar
  • 21
0 votes
0 answers
29 views

How to solve recurrences of this type?

$T(n) = 2 T(\lceil \frac{2n}{3} \rceil) + T(\lceil \frac{n}{3} \rceil) + O(n log n)$ From the 3-ary recurrence tree, one can say that $T(n) \geq cnlog^{2}n$ for some constant c, using the shortest ...
Biggo's user avatar
  • 1
0 votes
3 answers
111 views

How do I solve this recurrence equation?

I have to express the solution of the recurrence equation T(n) = T(an) + n where a is a constant, 0 < a < 1, in terms of θ using the iteration method. I am unsure of how I calculate the cost of ...
afahey03's user avatar
0 votes
1 answer
41 views

A Problem with Solving a Recurrence relation

I Hope someone Can help me with that: $T(1)=2$ $T(n)=\left(T(\frac{n}{2})\right)^2\cdot2^n $ what is the runtime complexity of the algorithm (base 2) Thanks a Lot!
Bubi's user avatar
  • 1
-2 votes
1 answer
36 views

Solving a recurrence relation formula with squared

I hope someone can help me with that: $$T(n)=T(2^{\sqrt{\log n}})+1$$ I will be asked to answer what is the runtime complexity of the algorithm. I tried to set m=2^ and still failed.
Bubi's user avatar
  • 1
0 votes
2 answers
45 views

Dropping terms in proving the runtime for a recurrence?

I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this: Recurrence: $...
gorilla_glue's user avatar
0 votes
1 answer
43 views

Algorithm Asymptotic Analysis

I'm trying to solve this time complexity: $T(n) = 2T(n-2) + n$, but having some challenges addressing the $(-2)$ component. Any insights on this complexity? Ended up with a section $[2^2\cdot1 + 2^3\...
cch's user avatar
  • 1
0 votes
3 answers
143 views

How to write recursive function in pseudocode for this number $a_n=n!+2^n$

I need to write recursive function in pseudocode for n-th number term of $a_n=n!+2^n$. Whole code should be contained in one function with $n$ as function argument.
DScounterGO's user avatar
-4 votes
1 answer
52 views

How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2

How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2
Aziz's user avatar
  • 1
4 votes
2 answers
1k views

Does T(n) = 2 · T(2n) + n apply to Master method?

I'm trying to apply the master method to the following recurrence: $$T(n) = 2 \cdot T(2n)+n.$$ We have $a=2$ and $b=1/2$. Also, $f(n)=n$ and $n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$ since $\log_{1/2}...
Jarvis's user avatar
  • 99
-1 votes
1 answer
81 views

Modified Quickselect - Proving linear time

As we know, Quickselect chooses a 'random' element in order to partition the array around that element in every iteration. Assume the random element is at most the $\frac{1}{k}\cdot n$ largest element,...
Aishgadol's user avatar
  • 315
-1 votes
2 answers
963 views

T(n) = 2T(n/4) + sqrt(n)

T(n) = 2T(n/4) + sqrt(n) I am trying to solve this question and ended up with the answer O(√n.log√n). But when I checked online the answer was supposed to be O(√n.logn) or √n.logn base 4. I am not ...
Crack_on_life's user avatar
1 vote
0 answers
51 views

Runtime of this algorithm

I have an algorithm with running time that satisfies $$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
Keio203's user avatar
  • 257
0 votes
0 answers
29 views

Solving a recurrence relation using the Master Theorem

I'm trying to solve this recurrence relation: $T(n) = T(\frac{n}{2}) + T(\frac{n}{5}) + T(\frac{n}{10}) + c_1n$ ; n > 1 $T(n) = c_2n$ ; n = 1 My first thought was to combine the fractions and ...
user avatar
0 votes
1 answer
37 views

Recurrence Relation Proof check

A question I was given $T(0) = 1,$ $T(1)=0,$ $T(n)= 2T(n-2)$ I think the possible solution is $T(n)=2^n$ Proof: by induction. Base Case: $n=0$ $T(0)=2^0=1$ Inductive Hypothesis: Assume for some $n$. $...
KetDog's user avatar
  • 157
0 votes
0 answers
106 views

Prove that the total number of parenthesizations of n matrices is Ω(4^n/n^3/2)

Is it possible to prove the total number of parenthesizations of n matrices is Ω(4^n/n^3/2) using the Induction Method? Recurrence formula from CLRS book When n = 1, the sequence consists of just one ...
learner_b's user avatar
0 votes
1 answer
136 views

In merge sort, what will be the time complexity if in each recursion, we break the array in two parts of size 1/4 and 3/4 respectively?

Let's say number of elements are a power of 4. Now if we break the array in parts of 1/4 and 3/4, how do we calculate the time complexity in this case?
Anmol Gupta's user avatar
0 votes
2 answers
73 views

Finding the runtime out of a recursion formula when using divide-and-conquer

In divide-and-conquer, one uses the following formula to find the runtime: $$T(n) = aT(n/b) + f(n).$$ I am confused with the meaning of the constants $a$ and $b$, as well as by the question of how to ...
user153448's user avatar
-3 votes
1 answer
66 views

How to solve T(n)=2T(√n)+(loglogn)^2?

Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part
Chris W's user avatar
0 votes
2 answers
73 views

Recurence Relation, specifically understanding substitution rule used

This is a pretty vague question and can be applied to many math problems not just recurrence relations. Above I fully understand, setting up the recurrence relation from the algorithm given. And how ...
ZenPyro's user avatar
  • 23
-1 votes
1 answer
164 views

Help me solve recursion equation by using recursion tree method

Hello I am trying to solve this recurrence equation using the recursion tree method: T (n) = T (n −1) + n^2 In particular, what is big-O of T (n)? Here is what I have done so far: I am not sure if I ...
Mario's user avatar
  • 3
1 vote
1 answer
76 views

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

Suppose given the recurrence $$T(n)=T(\frac{n}{2})+\frac{n}{\log n}.$$ I think the answer is $$T(n)=O\left(\frac{n}{\log n}\right).$$ because $$T(n)=T(1)+\sum_{i=0}^{\log n-1} \frac{n}{2^i(\log n-...
user1090604's user avatar
-3 votes
2 answers
51 views

Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$

Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.
Xited's user avatar
  • 1
-1 votes
1 answer
82 views

How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?

Suppose you have to prove the solution to the following recurrence by Induction, $$ T(n)= \begin{cases} \Theta(1), & n=1 \\ 2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1 \end{cases} $$ Here, $\...
Jamāl's user avatar
  • 179

1
2 3 4 5
15