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
0answers
22 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
25 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
54 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
12 views

What is the answer for this recurrence? Is there a way to solve it? How? @

Solve the recurrence $T_n = 4T_{n+2} + n + 1$ where $T_1 = 0$ for $T_i = 1, 2 ... 16$
0
votes
0answers
12 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
votes
0answers
13 views

Recursive definition character counter

This is my definition for part 1 (in latex form) \begin{alignat*}{2} \text{Base Case }& &&\text{ if } \mathtt{ones}(\varepsilon) = 0 \qquad \mbox{ ($\varepsilon$ is the empty ...
1
vote
1answer
14 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
43 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
73 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
51 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
118 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
39 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)
1
vote
1answer
26 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
41 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
66 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
28 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
125 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
32 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
46 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
81 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
26 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(...
1
vote
1answer
20 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
22 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
23 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
33 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
32 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
86 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
40 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
96 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
356 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
116 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
56 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
51 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(...
2
votes
1answer
58 views

How to prove a bound function for a sequence of numbers?

Let $G_n$ be defined by $$G_n = \begin{cases} 1 & n=0 \\ 2 & n = 1 \\ 3 & n = 2 \\ 4 & n = 3 \\ 2G_{n-1}-2G_{n-3}+G_{n-4} & n\geq4 \end{cases}$$ How can I prove that $f(n) = n$...
1
vote
1answer
41 views

Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$

Consider the recurrence $$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$ I tried to solve this as follows. First, I found the homogeneous solution: $$ a_n^{(h)} = r^2 - 3r + 2r \\ (r-2)(r-1) = 0 \\ ...
0
votes
0answers
36 views

How can I prove the linear time search algorithm takes O(n) time? [duplicate]

The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
0
votes
0answers
34 views

Meaning of polynomially larger, / smaller and meaning of polynomial larger / polynomial smaller

Hi I have spent the last two hours trying to find a general definition for both of these terms, but it seems like in computer science, people do not really agree on definitions. And I haven't even ...
0
votes
1answer
60 views

Closed form solution of $T(n) = 5T(n-1) + n^2$ [duplicate]

How to find the closed form solution of this equation? Is there a repeatable pattern for solving this equation? $$T(n) = \begin{cases} 1 & n = 1\\ 5T(n-1) + n^2 & \text{otherwise} \end{cases}$...
2
votes
2answers
250 views

Finding recurrence relation for running time of an algorithm

I am pretty new to this, consider the following algorithm: ...
0
votes
0answers
38 views

Substitution method for $T(n) = 2T(7n/10) + O (1)$ [duplicate]

I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method. I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.
3
votes
2answers
102 views

How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?

The recurrence I have is $T(n) = 2T(\sqrt{n-1} + 2) + 1$ I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm ...
1
vote
0answers
83 views

What are the asymptotic bounds (upper bound on time complexity) of the following function?

I am trying to find the upper bound on time complexity of the recursive function defined by the following equation: $$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
0
votes
2answers
60 views

Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?

To make my question more concrete, here is an example I am stuck on. I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$...
3
votes
0answers
47 views

Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in: $$ T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
1
vote
3answers
112 views

Solving $T(n)=4T(n/2)-1$ without using the master theorem [duplicate]

How can I solve the following recurrence without using the master theorem? $T(n)= 4T(n/2)-1$ for $n>4$ and $T(n)=5$ for $n\le 4$, $n$ is a power of $2$.