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
2
votes
1answer
24 views

How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method

Show by induction that any solution to a recurrence of the form $ T(n) \le 2T(n/3) + c\log_3 n $ is $O(n\log_3 n)$. Hoping someone can help me with the correct solution. I attempted two ways to ...
1
vote
1answer
22 views

Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms

While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type : $$\begin{cases} T(n) = \Theta(1), & \text{for small enough $n$;}\\ T(n) \leq T(a_n n + h(...
1
vote
2answers
34 views

Master Theorem applicable here?

Let $T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\ 1 & \text{if }n=1 \end{cases}$ I need to prove that $t(n) \in ...
1
vote
1answer
21 views

Proving van Emde Boas recurrence

I have tried to solve the following question: van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$. ...
1
vote
1answer
37 views

Solution of CLRS question 4.6-2

I am trying to solve the 4.6-2 question in CLRS book which is $T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$ While solving the above equation I reach the following point: $T(n)= n^{\log_ba} + n^{\...
0
votes
0answers
9 views

L-System coordinate conversion (as opposed to drawing): Extending the Hilbert Space Filling Curve

I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
1
vote
1answer
25 views

Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$ How can I prove by induction that this is $\Omega(n^2)$? I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$
1
vote
1answer
38 views

Finding a closed formula for recurrence relation

I'm trying to find a closed formula for the below recurrence relation: For the first one, $n$ is some power of 2 $$T(n) = \begin{cases} 4 & \text{if $n=1$} \\ 2T(\frac{n}{2}) +4 & \text{...
0
votes
0answers
17 views

O nation prove with limit theroem? [duplicate]

I'm working on my school homework,even though i found all three of these. It says use limit to compare. I confused , what should i do, i mean its obvious C A B
1
vote
1answer
30 views

Relaxing hypotheses of Master Theorem

This question is related to Master Theorem on oscillating function. Consider a recurrence of the form $T(n) = a T(n/b) + f(n)$ Master Theorem's regularity condition excludes some cases (for example,...
0
votes
0answers
62 views

How to solve this recurrence relation using substitution method

Can anyone explain to me how to demonstrate that, $$T (n, d) ≤ T (n − 1, d) + O(d) + d/n (O(dn) + T (n − 1, d − 1))$$ is solved by $$T (n, d) ≤ bnd!$$ for some constant $b$ using the substitution ...
1
vote
1answer
34 views

Why $T(n)=6T(n-1) + n^3$ has such a mess solution?

I tried to solve the recurrence relation $T(n) = 6T(n-1) + n^3$ using the tree method, and figured out that the root will be $n^3$, the second level will be $6^1(n-1)^3$, the third will be $6^2 (n-2)^...
0
votes
1answer
16 views

How to represent a recurrence that increments by one at each tree level?

I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows: $$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$ I ...
1
vote
2answers
36 views

Is master theorem applicable for $T(n) = 8T(\frac{n-\sqrt n}4) + n^2$?

Is master theorem applicable for this example? $$T(n)= 8T \biggl(\frac{n-\sqrt n}4\biggr)+ n^2$$
0
votes
1answer
38 views

Runtime of Divide and Conquer Flavored Bogo Sort

Here we propose a way to reduce Bogo Sort's runtime from factorial to exponential using a divide and conquer approach. This is something we have likely all pondered on extensively. https://en....
0
votes
1answer
27 views

How do I design a DP algorithm to count the minimum amount of continuous palindromic subsequences in sequence?

Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm. I am ...
1
vote
1answer
25 views

Calculating complexity for recursive algorithm with codependent relations

I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes: F(n) = F(n-2) + 2*G(n-1) G(n) = G(n-2) + F(n-1) ...
0
votes
1answer
52 views

Solving the recurrence of recursive insertion sort

I have solved that the recurrence of running time of the algorithm given as $$ T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases} $$ So the ...
0
votes
1answer
40 views

Minimal number of changes to make string into concatenation of $k$ palindromes

The following question is taken from leetcode: 1278. Palindrome Partitioning III You are given a string $s$ containing lowercase letters and an integer $k$. You need to: First, change some ...
2
votes
1answer
41 views

Number of parenthesizations and Catalan numbers

I read in CLRS that the number of possible parenthesizations for a product of $n$ matrices is given by the recursive formula: $$ P(n)= \begin{cases} 1 & \text{if } n = 1,\\ \sum^{n-1}...
1
vote
1answer
39 views

Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$

Is there a way to solve this recurrence using master theorem: $$T(n) = 4T(n/2) + Θ(n^2/\log n)$$
2
votes
1answer
24 views

“Unrolling” a recurrence relation

int function(int n) { int i; if (n <= 0) { return 0; } else { i = random(n - 1); return function(i) + function(n - 1 - i); } } ...
0
votes
0answers
30 views

Asymptotics of reccurence relation

I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$ $T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\ \forall n<10 \quad T(n) = 1$ And if there is such $a$ I need to find the ...
2
votes
1answer
23 views

Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time

The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce ...
1
vote
1answer
13 views

Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as ...
0
votes
0answers
22 views

Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, ...
1
vote
2answers
50 views

Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$

Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$. I will make the bound to be $\in O(cn)$ instead. Proof by strong induction. Base case n =1 ...
1
vote
0answers
45 views

How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I want to solve the following using master theorem. $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$ I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$ I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$ I ...
1
vote
0answers
26 views

Find the upper bound of the recurrence T(n) = T(n - 4) + n with n is odd

I am trying to solve this recurrence assuming n is odd: $T(n) = T(n - 4) + \Theta n$ What I did so far was: First, $T(n - 4) = T(n - 8) + (n - 4) $, thus we get $T(n) = T(n - 8) + (n - 4) + n$ Next,...
2
votes
1answer
32 views

Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
0
votes
1answer
22 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
51 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
36 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
42 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. ...
2
votes
2answers
81 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
71 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
41 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
128 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
58 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
165 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
128 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
61 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
188 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
50 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
29 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
33 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
75 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
47 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
22 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
60 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 \\...

1
2 3 4 5
11