Questions tagged [recurrence-relation]
a definition of a sequence where later elements are expressed as a function of earlier elements.
507
questions
0
votes
1answer
19 views
Converting a function with single parameter to a function with multiple parameters
I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:
Given a string or a list, do an aggregation operation on each of its elements. Here ...
0
votes
1answer
32 views
How can i solve a recursion equation with square root using recursion tree method?
$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$
I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.
I just don't want to ...
0
votes
1answer
35 views
Solving a peculiar recurence relation
Given recurrence:
$T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$
The way I solved is like this (using change of variables method, as mentioned in CLRS):
Let $n = 2^k$
$T(...
0
votes
1answer
28 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
2answers
55 views
Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)
Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
3
votes
1answer
67 views
Closed formula for two variable recurrence
I would like to know if there exists a closed form formula to the following recurrence:
$f(s, 0) = 1$
$f(s,b) = \displaystyle\sum_{i=1}^{min(s, b)} \left[
(s-i+1)\times f(i, b-i) \right] $
This ...
1
vote
1answer
32 views
Solving a recurrence relation with T(n) = 2 * T(n/3) + 5n [duplicate]
I have no idea how to solve this one - I end up with $\sum_{i=0}^k (2^k * 5 * 3^i)$ but I have no clue how to get any further than that (e.g. resolve the sum even further, if it's even correct to ...
1
vote
1answer
43 views
Recurrence relation and time complexity of recursive factorial
I'm trying to find out time complexity of a recursive factorial algorithm which can be written as:
fact(n)
{
if(n == 1)
return 1;
else
return n*fact(n-1)
}
...
2
votes
2answers
54 views
Summing $1,3,5,\ldots$
I solved a recurrence to get the formula $T(n) = \sum_{i=1}^{k}2i+1$ for $k = \frac{n-1}{2}$, namely
$$ T(n) = 1 + 3 + \dots + (n-4) + (n-2) + n, $$
but I'm not sure how to finish off the problem by ...
3
votes
2answers
114 views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
3
votes
1answer
108 views
Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems
I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences.
The first problem I solved was longest palindromic substring ...
1
vote
0answers
40 views
Egg dropping problem binomial coefficient recursive solution
I have a question about the binomial coefficient solution to the generalization of the egg dropping problem (n eggs, k floors)
In the binomial coefficient solution we construct a function $f(x,n)$, ...
2
votes
1answer
102 views
How to solve $T(n)= 4T(\sqrt n) +\log^2n$?
Consider the recurrence
$$T(n)= 4T(\sqrt n) + \log^2n. $$
I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.
1
vote
1answer
47 views
Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?
I am having difficulties in understanding why the recurrence
$$T(n)=3T(n/4) + n\log n$$
is solvable with Master Method but
$$T(n)=2T(n/2) + n\log n$$
isn't?
Despite they both look very similar ...
1
vote
0answers
28 views
Finding the closed form of this recurrence
We have the following recurrence $T$:
$$
T(n,k) = \left\{
\begin{array}{ll}
\alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\
T(\lceil n / 2 \rceil, k)...
1
vote
0answers
30 views
Hanoi towers recursive expression for EVERY algorithm
What the recursive algorithm for moving $n$ disks says, is:
If $n > 1$, move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n > 1$, move $n-1$ discs from B to C.
Let $T_n$ be ...
0
votes
0answers
62 views
Induction proof given recurrence of algorithm
I am having trouble starting this proof and wanted some clarification. Here are the details given:
...
0
votes
0answers
22 views
Time Complexity calculation using recursion tree method
What is the time complexity of the following recurrence equation :
T(n) = T(n/2) + T(n/4) + T(n/8) + n
I solved it using recursion tree method and I'm getting O(n) as the answer.
Please let me know ...
1
vote
1answer
16 views
Why can we ignore the constant factor in Weis's proof of the Master Theorem
In the 4th edition of his Data Structures textbook, Weis gives a proof of part of the Master Theorem. This proof says "Let us ... ignore the constant factor in $\theta(N^k)$ ... I don't understand ...
1
vote
0answers
50 views
How to prove a recursive's function Big-Theta without using repeated substitution, master theorem, or having the closed form?
I have a function defined: $V(j, k)$ where $j, k \in \mathbb{N}$ and $t > 0 \in \mathbb{N}$ and $1 \leq q \leq j - 1$. Note $\mathbb{N}$ includes $0$.
$V(j, k) = \begin{cases} tj & k \leq 2 \\...
4
votes
1answer
91 views
Solving $T(n) = 2T(n/2) + T(n-1)/\log n$
I am interesting in the asymptotic rate of growth of the following recursion:
$$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$
with base case $T(1) = 1$.
I'm having trouble of solving this recurrence ...
3
votes
1answer
84 views
Solving recurrence relation with different rules for odd and even n
Assume $T(1) = 1$, and
$T(n) = 2T(n/2) + n^2$ for even $n$,
$T(n) = T(n − 1) + n$ for odd $n$.
I'm new of learning to solve recurrence problem, for 1, it seems we can apply Master Theorem directly ...
1
vote
2answers
136 views
Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree
I am trying to solve the following recurrence relation:
$$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$
I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$
I ...
2
votes
1answer
42 views
Recurrence Question:T(n) = T(n − √ n) + T( √ n) + θ(n)
I need help to solve the recurrence T(n) = T(n−√n) + T(√n) + θ(n)
2
votes
1answer
46 views
Grokking pseudo-code for solution to gas station problem
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
2
votes
1answer
45 views
Solving a recurrence relation involving square roots
Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n. $$
How can I solve this recurrence relation, which involves square roots?
-1
votes
1answer
103 views
Recurrence Problem T(n) = 3T(n/3) + n
I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence:
$$T(n) = 3T(\frac{n}{3}) + n$$
How can I ...
0
votes
1answer
29 views
How is this equation (involving a recurrence and $\phi(N)$) derived?
As in another question, let
$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise}
\end{cases}$$
where $\phi(N)$ is Euler's totient function.
Tasse ...
1
vote
1answer
306 views
Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation
I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same ...
0
votes
1answer
44 views
Please provide me a solution of Max-Heapify using Recursion Tree
I tried my best to solve the recurrence relation.
$T(n) \le T(2n/3) + \Theta(1)$
Using the recursion tree.
I could reach out the boundary condition when at depth ...
1
vote
1answer
81 views
Solving recurrences (tree method) with square roots
I am trying to find the upper and lower bounds for this recurrence, but I am not sure how to handle to square root:
$$
T(n) = 4T(n/2) + n^2\sqrt{n}
$$
3
votes
1answer
93 views
Solve recurrence relation that depends on depth of recursion
The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is:
A frog is sitting on the edge of a pond facing ...
0
votes
0answers
28 views
Does the master theorem applies to this recurrence?
The recurrence:
$T(n) = pT(n/q) + \log n$
for p < q and p >= 2.
So, I've figured out it would fall into case 1, since we have $n^{log_{q}p} = n^r $, for $0<r<1$, which would mean that $f(...
2
votes
2answers
40 views
Complexity of iterative exponentiation
I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it:
The following function calculates $x^n$ ...
0
votes
1answer
23 views
Recurrent relation for algorithms with two stages
I am trying to do the recurrence relation for my algorithm, but it has two variables $T(n,m)$. For sufficiently small $n$, $m$ is practically the same as $n$, but $m$ cannot grow beyond some constant $...
1
vote
1answer
25 views
Solving recurrence relation where the $f(n)$ has some constant factor $k$ where $0 < k < 1$
I am trying to see if a recurrence relation where $f(n)$ has some constant factor $k$, e.g. $f(n)=kn$ where $0 < k < 1$, is $O(n)$. I am reaching a different result depending which route I take. ...
2
votes
1answer
38 views
evaluating time complexity of a code
I'm trying to evaluate the time complexity of the following :
...
1
vote
0answers
22 views
Useful conditions for proving super polynomial lower bound for some kind of recurrences
Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$
Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
1
vote
2answers
36 views
Complexity guess and induction proof
I was trying to prove by induction that
$$
T(n) = \begin{cases}
1 &\quad\text{if } n\leq 1\\
T\left(\lfloor\frac{n}{2}\rfloor\right) + n &\quad\text{if } n\gt1 \\
\end{...
1
vote
1answer
22 views
Recurrence Equation upper limit problem
I was looking at my teacher's notes and came about the following recurrence equation :
$$
T(n) =
\begin{cases}
1 &\quad\text{if } n\leq 1\\
4T\left(\frac{n}{2}\right) + n^3 ...
0
votes
2answers
34 views
Converting a Recurrence Relation to its Closed Form [duplicate]
I have a recurrence relation of the form given below (taken from Analysis of Algorithms - An Active Learning Approach by Jeffrey J. McConnell):
$T(n) = 2T(n - 2) - 15 $
$T(2) = T(1) = 40 $
I am ...
1
vote
1answer
113 views
Akra-Bazzi method integral diverges
I want to solve this recursion:
$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$
My attempt and issue:
None of the cases for master theorem apply here.
I tried using Akra-Bazzi method (https://en....
2
votes
2answers
44 views
How do we guess the recurrence relation from the given equation
In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is
\begin{equation}
T(n)=2 T(\lfloor n / 2\...
1
vote
1answer
103 views
Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$
The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on $$ T(n) = 9T(\sqrt[3]n) + \Theta(1). $$ I am able to get the tree started and find a pattern with the sub-...
2
votes
1answer
365 views
Solving recurrence relation with minimum and factorial
I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N_+\times\Bbb N_+$.
$T(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq 2(n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\...
1
vote
1answer
118 views
Recurrence with Minimum
I need to solve the following recurrece:
$T(n,m)=\begin{cases}
1, & m\leq 2(n-1)!\\
\min\limits_{a,b\geq 1\\a\cdot b\leq (n-1)!}{T(n-1,a)+T(n-1,b)+T(n,m-ab)}, & \text{else}
\end{cases}$
Note:...
2
votes
1answer
61 views
solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method
How can I solve $$T(n)=T(n-2)+\frac {d}{2}n^2$$
I couldnt find $d$ (dont know if I have to) and after 3 iterations I got to $k= \frac{n-1}{2}$
but had trouble to continue.
2
votes
2answers
58 views
Number of possible heaps on $\{1,…,2^h-1\}$
Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it.
Definition
A binary tree ...
0
votes
1answer
32 views
Trouble finding what this recurrence solves to [duplicate]
I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$
I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
2
votes
1answer
55 views
What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$ [closed]
Problem:
Find the closed-form expression for$$
T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1
\tag{1}
$$where $T_1 = 1 .$
Calculating this sum I came up with the following result:
$$
T_n = 8^{\left(...
