a definition of a sequence where later elements are expressed as a function of earlier elements.

learn more… | top users | synonyms

0
votes
4answers
45 views

Applying Master Theorem to: T(n) = T(n - 2) + n^2 [duplicate]

I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation: T(n) = T(n-2) ...
1
vote
2answers
53 views

How to connect the math of recurrence relations to daily programming concepts

What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear ...
-1
votes
1answer
23 views

Converting pseudo code to a recurrence relation equation? [duplicate]

The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(...
4
votes
1answer
43 views

Two recurrences for the change-making problem with repetition

The change-making problem with unbounded repetition is: Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$; and an amount $v$. Output: Can the given $v$ amount of money be ...
1
vote
2answers
88 views

Solving the recurrence T(n) = 4T(n/4) + n log n with the iterative method

I'm trying to solve $$ T(n) = 4T(n/4) + n \log_{10}n.$$ I'm having trouble with Iteration Method near the end. As far as I went, I obtained the General Formula as: $$4^kT(n/4^k)+n\log n+\sum (n/4^k)...
1
vote
0answers
27 views

$N$-th term of a quadratic recurrence [closed]

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ ...
0
votes
1answer
28 views

Runtime analysis with recursion factor

I have this code: if n is even { for i=1....n for j=1...i print j return 8*foo(n/2) } Asking to calculate the running time $T (n)$. I thought at first ...
2
votes
1answer
68 views

Reccurrence for the game of pile of stones

I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows: Two players are playing a game. There are $k$ piles of stones. When it is his turn ...
5
votes
1answer
99 views

Solving T(n) = 2T(n/2) + log n with the recurrence tree method

I was solving recurrence relations. The first recurrence relation was $T(n)=2T(n/2)+n$ The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree ...
3
votes
1answer
30 views

Solving recurrence relation when cost of all combining steps is constrained

I have a recurrence relation $T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n)$, where each $ 0 < d_i < 1$, $f(x) > 0$ for all $\, x > 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$. ...
3
votes
2answers
65 views

How to calculate the time complexity of a Catalan-like recurrence by substitution?

I was given the following problem: Calculate the computational time complexity of the recurrence $$P(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum_{k=1}^{n-1} P(k) P(n-k) & \text{if } n \...
0
votes
1answer
28 views

Solve Recurrence Relation

I'm trying to solve the following recurrence relation. I've gotten through two iterations, but I don't see any pattern. I would appreciate any help with this. $T(1)=1$ $T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$ ...
-1
votes
1answer
52 views

Solving $T(n)= 3T(n/4)+ n\log n$ without the master method [duplicate]

How can one solve $$T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log n$$ without using the master method? I know it has a solution using the master theorem from this link.
1
vote
2answers
61 views

Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C

So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve ...
0
votes
0answers
12 views

Does master theorem apply differently for $n$ with restrictions? [duplicate]

Given $T(1) = 1$ and $T(n) = 4T(n/2) +n^2$ for $n\geq 2$, can I solve the recurrence for $T$ by applying the master theorem with $a = 4$, $b = d = 2$? This would give $T(n) = \Theta(n^2\log n)$.
0
votes
1answer
20 views

Why do I need a base case for n=3 when solving a d&c recurrence?

I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example: $T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ where $T(1) = 1$ They assume ...
0
votes
0answers
26 views

How do I make the “+2” go away in the recurrence relation of T(n) = 4T(n/2 + 2) + n [duplicate]

$T(n) = 4T(n/2 + 2) + n$ How can I make the plus 2 disappear? I have been reading the answer to this and I'm having trouble understanding it. Can someone maybe show me step by step how I would do it....
1
vote
1answer
61 views
5
votes
2answers
93 views

Why does the recurrence equation for QuickSort consider all the elements in the array?

I have been taught that QuickSort has the following recurrence equation in the best case: $T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \...
13
votes
3answers
2k views

How long does the Collatz recursion run?

I have the following Python code. ...
2
votes
2answers
74 views

Trying to find a substitution to solve a recurrence

I'm trying to solve the following recurrence. \begin{align*} B(2) &= 1\\ B(n) &= B(\lceil n / \log_2 n\rceil)+\Theta(n) \end{align*} Here is my attempt: \begin{align*} B(n) &= 3B(\...
0
votes
0answers
30 views

Complexity of solving recurrences

What is the complexity of the following problem? I can see it's in NP for reasonable definitions of closed form, is there anything else one can say about it? Given a recurrence relation $R_0 = \...
0
votes
0answers
15 views

What are the recursive relations for these max/min methods. [duplicate]

So basically I have two methods that find the max and min. The first one splits the array into n/2 and n/2 parts and continues to split the parts until there are only pairs of 2 or single values. The ...
-1
votes
1answer
67 views

Complexity and Recurrence relation for Lowest Common Ancestor Binary Tree

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest ...
0
votes
1answer
47 views

How to properly solve T(n) = T(n-1) + O(2^n)?

I've been trying to solve this recurrence: T(n) = T(n-1) + O(2^n) My approach when writing everything out and solving the geometric series was: T(n) = O(2^n). T(n) = c2^n * (1 + 1/2 + 1/4 + ...) = ...
0
votes
1answer
65 views

Prove by induction that the running time of recursive Fibonacci is exponential

This example followed from a Fibonacci algorithm in class. The professor showed us how to compute $T(n) = T(n-1) + T(n-2) + 3$, but left this step for us to prove, so I decided to attempt to prove it! ...
3
votes
1answer
66 views

Proof for Minimum number of insertions to convert a string to a palindrome

For the problem "Find the minimum number of insertions to convert a string $S$ to a palindrome", a recurrence relation usually given is: $$ c[i,j] = \begin{cases} c[i+1,j-1] & \text{if } S[i] = S[...
6
votes
2answers
101 views

Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the “+1” part?

I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain ...
1
vote
2answers
50 views

Find Big O using Iteration

I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step. $T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ ...
1
vote
2answers
190 views

Using the Master theorem on a recurrence with non-constant a

I am trying to solve the following equation using master's theorem. $T(n) = 3^n T(\frac{n} 3) + O(1)$ Extracting the b and $f(n)$ values makes sense they are $b=3$ and $f(n)=1$. I am not sure what ...
3
votes
1answer
65 views

Solving the recurrence $T(n)=T(n-1)*T(n-2)$

I have been trying to solve the following recurrence: $$T(n)=T(n-1)*T(n-2)$$ The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$. I started by taking the $\log_{2}$ of both sides to ...
0
votes
0answers
31 views

Efficient algorithm for swapping dimensions for an N-dimensional matrix

I have data stored in N-dimensional matrixes (i.e. Arrays nested N layers deep). Is there a good standard solution - other than brute force - to the following two problems I want to swap 2 ...
1
vote
1answer
44 views

Number of levels in the recursion tree

While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log_{b}n$ when $b$ is a constant....
7
votes
1answer
134 views

What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037. This is my proposed solution to compute the $n$th value: ...
2
votes
2answers
86 views

Recurrence relations when function call is made inside loop

int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n – k); return x; } What is the value of fun(5)? I ...
0
votes
1answer
34 views

Reccurrence equation and finding suitable algorithm

I'm given the following recurrence equation: $$\begin{align*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n > 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && \...
-2
votes
1answer
45 views

Recurrence for the number of strings defined by a homomorphism

Let $h$ be the homomorphism defined by $$ h(a) = \mathtt{01}, \quad h(b) = \mathtt{10}, \quad h(c) = \mathtt{0}, \quad h(d) = \mathtt{1} $$ and extended to strings in the usual way. Then the inverse ...
0
votes
0answers
13 views

Q: Resources where i can practice creating recurrence relations from code? [duplicate]

I'm having difficulty creating recurrence relation from (pseudo)code. Are there any recommendations or resources I can use to get better?
7
votes
1answer
399 views

Big-O proof for a recurrence relation?

This question is fairly specific in the manner of steps taken to solve the problem. Given $T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$. So the steps were as follows. We want to prove that $T(n) \...
4
votes
1answer
66 views

How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$

I am basically trying to solve the following question: Given a set $P = \{\{1\},\{2\},\dots,\{n\}\}$ of $n$ sets of elements, our aim is to merge these elements into one set. At each step, sets can ...
1
vote
0answers
29 views

Understanding exponential computation by digit recurrence

I've met in a book the following algorithm that computes the exponential: Input: $t, n$ ($n$ is the number of steps) Output: $E_n$ $\begin{array}{l} \mbox{define $t_0 = 0$ ; $E_0 = 1$} \\ \mbox{...
0
votes
1answer
78 views

How to solve $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$? [duplicate]

How do I solve the recurrence relation $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$, for constant $k$? I am told that the answer does not depend on $k$.
4
votes
1answer
82 views

Solving recurrences by substitution method: why can I introduce new constants?

I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is: Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$ So, by big-O definition I ...
-2
votes
1answer
31 views

Time complexity of a Divide and Conquer

I have Master theorem for finding complexities but the problem is Master theorem says For a recurrence of form $T(n) = aT(n/b) + f(n)$ where $a \geq 1$ and $b > 1$, there are following three cases:...
2
votes
1answer
55 views

Master method recurrence question [duplicate]

This is specifically a question pertaining to solving reccurences via the Master Theorem/Method, particularly for a specified $f(n)$ (as denoted below). For a recurrence of $$T(n) = a T(\frac{n}{b}) +...
1
vote
0answers
28 views

Solving a recurrence relation [closed]

I am having problem with solving the following recurrence relation. $A$ is a set, there are at most $k+1$ of this set and $|A|$ is at most $n/2$. $T(n) = O(n log k) + \sum_A T(|A|)$ I guess it can't ...
0
votes
0answers
14 views

Evaluate run time and compare these algorithms [duplicate]

Algorithm A divides the problem into 5 sub-problems of half the size. Solving each sub-problem then combining the solutions in linear time. Algorithm B solves problems of size n by dividing them into ...
0
votes
1answer
61 views

How to deal with $n\sqrt n$ in master theorem?

In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$ $T(n) = 8T(n/4) + n\sqrt n$ How do I handle $n\sqrt n$ in this case to get $d$ ...
3
votes
1answer
55 views

How do I find an upper bound on this recurrence

$f(n)=f(n-\sqrt{n})$ I believe $f(n)\in O(\sqrt{n})$ However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks ...
0
votes
1answer
54 views

Recurrence Relation(with Square root)

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $ with initial values $T(0) = T(1) = 1$ Any helps on how to find it