Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
724
questions
0
votes
1
answer
25
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] ...
- 1
1
vote
2
answers
57
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 ...
- 151
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}+...
- 55
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^....
- 55
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:
...
- 151
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,
...
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}{...
- 151
3
votes
1
answer
89
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 ...
- 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}
\...
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 ...
- 151
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 ...
- 151
0
votes
1
answer
54
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 ...
- 3
1
vote
2
answers
141
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 ...
- 151
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 <...
- 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) =...
- 121
0
votes
1
answer
58
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{...
- 113
1
vote
2
answers
63
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 ...
- 113
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 ...
- 113
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) ... ...
- 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$) $...
- 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 ...
- 1
0
votes
0
answers
381
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. ...
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] ...
- 103
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 ...
0
votes
0
answers
152
views
Recurrence relation for TSP using recursion
This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph:
...
- 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 $...
- 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 ...
- 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 ...
- 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 ...
- 1
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!
- 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.
- 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: $...
- 103
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\...
- 1
0
votes
3
answers
142
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.
- 11
-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
- 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}...
- 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,...
- 315
-1
votes
2
answers
953
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 ...
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 ...
- 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 ...
user154475
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$. $...
- 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 ...
0
votes
1
answer
134
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?
- 101
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 ...
- 113
-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
- 1
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 ...
- 13
-1
votes
1
answer
161
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 ...
- 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-...
- 11
-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.
- 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, $\...
- 179