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

learn more… | top users | synonyms

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
37 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
34 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 + ...) = ...
-1
votes
0answers
57 views

Limit of the sequence defined by a recurrence [migrated]

Given a recurrence formula for an arithmetic sequence, $$U_{n} = \frac{1}{2+U_{n-1}}$$ Show that$$\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ ...}}}} = (SomeGivenValue)$$ How can we solve questions ...
0
votes
1answer
45 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
39 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] = ...
5
votes
3answers
87 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 ...
0
votes
2answers
36 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
146 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
48 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
27 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
36 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 ...
6
votes
1answer
110 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
61 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
31 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
43 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?
8
votes
1answer
376 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
57 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
27 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
46 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$.
3
votes
1answer
73 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
28 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
52 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
27 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
57 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
49 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
65 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
56 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 ...
3
votes
1answer
38 views

About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]

In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather*} C_N = N + 1 + ...
1
vote
1answer
104 views

Solving a bivariate recurrence equation

I'm dealing with this recurrence equation: $\qquad\displaystyle T(m, n) = T(m/2, n/2) + T(m, n/2) + O(1)$. Any idea how to solve this? I've looked in to few advanced resources but the literature on ...
3
votes
2answers
119 views

Closed form for the recurrence T(n) = T(n-1) + n²

Given the following recurrence: $$ T(n) = T(n-1) + n^2$$ How can I prove it to be $O(n^3)$ with the substitution method? The $O(n^3)$ guess derives from the fact that at every step of the recursion ...
1
vote
0answers
27 views

how to solve recurrence T(n) = 2T(n/2)+n using substitution method [duplicate]

The required solution is given. I have to prove that its solution is $O(n\log n)$. My idea is shown below: I have to prove, $T(n) \le cn\log n$ for some constant $c$ $$\begin{align} T(n) &\le ...
0
votes
1answer
42 views

Complexity calculation using a recurrence relation [duplicate]

I just can't solve this problem, I'm new to reccurences. I have this recurrence $T(n)=n*T(n-1)$ $T(1)=1$ The second term will be: $T(n-1)=(n-1)*T(n-2)$ And so on. It's complexity is O(n!) but i ...
2
votes
1answer
34 views

Recurrence relation complexity [duplicate]

I just learned about recurrences and I just can't solve this problem. I have this recurrence relation: $$ T(n) = \begin{cases} k\cdot T(\frac{n}{k}) & n > 0\\ 1 & n = 0\\ \end{cases} $$ ...
1
vote
1answer
1k views

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

See title. I'm trying to apply the method from this question: http://stackoverflow.com/questions/13674719/easy-solve-tn-tn-1n-by-iteration-method. What I have so far is this, but I don't know how to ...
4
votes
1answer
75 views

Cases of Master Theorem

Suppose that we have $ \\ T(n)=\left\{\begin{matrix} c, & \ \text{if } n<d\\ aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d \end{matrix}\right.$ The Master theorem is the ...
0
votes
0answers
19 views

Solving $T(n)=2T(n/2) + n \lg n$ , For ex: Counting inversions implemented with full mergesort [duplicate]

How to solve the recurrence equation $T(n)=2T(n/2) + n \lg n$ For ex: I implemented "Counting inversions" with a full mergesort instead of just using merge part, So the outer complexity will be $n ...
1
vote
0answers
48 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
2answers
328 views

Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

http://www.algorithmist.com/index.php/UVa_10918 The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the ...
0
votes
0answers
20 views

Master Theorem applied to recurrence relations [duplicate]

Can anyone explain how to use the master theorem to the following problem... $$T(n) = T(\frac{n}{3}) + \log(n)$$
1
vote
1answer
101 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
0
votes
1answer
86 views

T(n/3) + log(n)

how do you find the Theta of this problem... $$T(n) = T(\frac{n}{3}) + \log_2(n)$$ I end up getting a pattern of $$T(\frac{n}{3^{k}}) + \log_2(\frac{n}{3^{k-1}}) + \log_2(\frac{n}{3^{k-2}}) + ... + ...
1
vote
1answer
65 views

Recurrence relation chip and conquer

Can anyone explain how to find the $\Theta()$ of this equation... $$T(n) = 3T(n-4) + cn$$ When I solve this problem I get this using the $k$ -th iteration... $$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) ...
2
votes
0answers
20 views

Asymptotic of interesting recurrence relation [duplicate]

I want to study the asymptotic behavior of the following recurrence relation: $y_1=1$; $y_{n+1}=y_{n}+(1+\frac{y_n}{n})^{-n}\ \ $ for $n\ge 1$. I made an initial attempt and guessed that $y_{n} ...
0
votes
0answers
13 views

runtime-analysis, runtime of this equation [duplicate]

Recurrence relation How can I determine the theta of this equation ? T(n)=3T(n/3)+3^(n/3) ,T(i) = 0 if i <0 My teacher gave me this clue : 2<=i<=log(base3)(n) and : for n>50 3^( ...
0
votes
1answer
76 views

Running time of recursive algorithm with geometric series

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
0answers
15 views

Running time of recursive algorithm [duplicate]

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...