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

learn more… | top users | synonyms

1
vote
0answers
25 views

$N$-th term of a quadratic recurrence [on hold]

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$ ...
-1
votes
0answers
8 views
-3
votes
0answers
10 views

recurrence relation using iterative method [duplicate]

SOLVE THE FOLLOWING recurrence relation using iterative method and give answer at the end in asymptotic form (show all possible steps) T(n)={■(1&if n=1@4T(n/4)&otherwise)}
0
votes
1answer
27 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
58 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
89 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
57 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
27 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
48 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.
0
votes
0answers
9 views

Recurrence for number of ways to write n as the sum [migrated]

I'm trying to find the recurrence for this problem: ...
1
vote
2answers
60 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 ...
1
vote
1answer
59 views
5
votes
2answers
92 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
71 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) &= ...
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
64 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
46 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
64 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
62 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] = ...
6
votes
2answers
99 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
48 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
184 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
63 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
42 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 ...
7
votes
1answer
132 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
83 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
395 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
63 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$} \\ ...
0
votes
1answer
76 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
81 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 ...
2
votes
1answer
54 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
60 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
0
votes
0answers
89 views

Proving a dynamic programming recurrence for coin exchange correct

Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins. I came into the following formula: $$ T(n,S) = ...
-3
votes
1answer
70 views

time complexity analysis of recurrence relation [duplicate]

I am not able to solve time complexity analysis of this recurrence relation: T(n)=3T(n/2)+n^2.I want to find time complexity analysis of this recurrence relation without using masters theorem could ...