Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

learn more… | top users | synonyms

1
vote
0answers
41 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
0
votes
0answers
13 views

Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
1
vote
3answers
61 views

Recurrence solution of simple recurrence

Please help me to find the solution of the recurrence in terms of n(implies $(f(n))$ and also the summation of the recurrence up to infinity ($sum = \sum_{n=0}^\infty f(n)$) . ...
6
votes
3answers
197 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
2
votes
4answers
111 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
1
vote
2answers
168 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
5
votes
2answers
195 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: $g(1) = \alpha;$ $g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
0
votes
0answers
13 views

Strassens Matrix Multiplication Algorithm to compute product of 2 4X4 Matrices

Im trying to learn starssens matrix multiplication Algorithm.So far i know that it uses 7 multiplications and replaces a multiplication by several additions and subtractions,to achieve better ...
1
vote
1answer
207 views

Dynamic Programming— Variable Width Bin (Equi-Depth) Histogram

Given some data, and a fixed number of bins (k)-- How can I design a Dynamic Programming algorithm that minimizes the largest difference between bin sizes? In other words, with a set number of bins ...
2
votes
1answer
31 views

Primitive-recursive functions and polynomial equations

I am looking for examples of primitive-recursive functions $f:\mathbb{N}\rightarrow\mathbb{N}$ that can not be written as a pair of polynomials, i.e. $$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$ ...
3
votes
1answer
182 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
0
votes
0answers
16 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
0
votes
0answers
14 views

Comparing Generalized Continued Fractions

Gosper lays out a method (under Approximations) for comparing regular (a.k.a simple) continued fractions which have all partial numerators set to 1. Continue comparing terms until they differ, then ...
0
votes
0answers
16 views

Question about set and series notation in the GSP Algorithm

I tried this in programming forums with no luck and since my primary issue is with the notation, I'm asking here: I have the definition of the GSP Algorithm: Definition However I don't understand ...
2
votes
0answers
26 views

Recursive Least Square (RLS) algorithm for regression. [closed]

What is meant by convergence of recursive least square (RLS) in online regression ?
1
vote
1answer
28 views

Solving a second level functional equation over all functions $g$

I am trying to find a closed form expression $f$ such that $$f(g(x+1) - g(x)) + f(g(x) - g(x-1)) = f(g(x))$$ For all functions $g$ I have concluded that for polynomials $$2^{n+1}f(0) = f(a_0 + ...
3
votes
1answer
72 views

Limit of a recursiv trigonometric function

So while doing my math homework I recently stumbled upon this little thing: It seems that $y_n = \sin(y_{n-1}) + k$ with arbitrary $y_0$ and $k$ converges to a definite value for $n \to \infty $. ...
0
votes
2answers
43 views

Wine problem - ratio and mixture

Question $8$ litres are drawn from a cask full of wine and is then filled with water. This operation is performed three more times. The ratio of the quantity of wine now left in cask to that of the ...
0
votes
0answers
14 views

Understand and an algorythm to Maximize number of triangles from a set of points on XY plane

Given: Set of points (x, y) Looking to: Maximize count of triangles that can be formed. Each triangle which is enclosed within another (with/without shared edge) will be counted again. Specifics on ...
1
vote
0answers
47 views

“Building blocks” for computable functions

In an (otherwise very enlightening) answer to another question of mine the question came up What functions are allowed as building blocks for computable functions? I was astonished that there ...
2
votes
0answers
77 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
1
vote
2answers
29 views

Finding the inhomogeneous solution

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
1
vote
1answer
50 views

How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
0
votes
2answers
35 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
1
vote
1answer
37 views
2
votes
1answer
63 views

Algorithm - iterative method

I'm stuck on an exercise on algorithms, can you help me with this exercise? Solve this recursion using iterative method. $$T(n) = \begin{cases}1 & n=1;\\ 2, & n=2;\\ T(n-2) + n/2,& ...
0
votes
4answers
560 views
1
vote
1answer
25 views

recursive relation for putting signs in 2*n table

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that? ...
0
votes
0answers
17 views

Derivation of Recursive Least Squares with Forgetting Factor

I have the following set of equations: $\begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_n \end{bmatrix} = \begin{bmatrix} a_1 \theta_1\\ a_2 \theta_2\\ \vdots\\ a_n \theta_3 \end{bmatrix}$ In the ...
2
votes
0answers
113 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
2
votes
0answers
37 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
0
votes
1answer
36 views

Number Triangle pattern

I have a number triangle as follows: $$\begin{array}{|c|c|c|} \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline 0 ...
0
votes
1answer
29 views

Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
-2
votes
1answer
38 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
2
votes
2answers
46 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
4
votes
1answer
43 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
0
votes
1answer
57 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
2
votes
1answer
22 views

How would I go about converting $U(n)= 4^n+U(n-1)$ into an explicit form? [closed]

I have the recursive function $U(n)= 4^n+U(n-1)$, and I'd like to convert it into an explicit form. If you could also walk me through the process that would be great. Thanks!
2
votes
2answers
59 views

Master theorem, algorithms $T(n) = 2T(n/3) + \log n$

Can I solve $ T(n) = 2T(n/3) + \log n $ using the master theorem?It doesn't seem to fit in any case.
0
votes
1answer
35 views

Find a linear-time algorithm for finding if element occurs n/4 times

Give a linear-time algorithm that determines whether an unsorted sequence of n real numbers contains a number that occurs at least n/4 times in the sequence. You algorithm should report “no” if ...
7
votes
6answers
617 views

Non-literal applications of “Shortest Path” algorithm?

It's obvious that it's used in stuff like Google Maps, but what are some more metaphorical applications where you're minimizing the path between nodes (which can represent anything)
-4
votes
1answer
38 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
-1
votes
1answer
45 views

How should I proceed to solve this recurrence relation: $T(n) = T(n - 1)^2$

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern. $$ T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} ...
4
votes
0answers
59 views

Four for loops in Matlab — optimize for speed

Let $s$ be a constant integer. I am computing a four dimensional matrix $A$ of size $(s+1)^4$ with entries in $[0,1]$. For this computation we use a three dimensional matrix $B$ of size $(s+1)^3$ with ...
1
vote
0answers
43 views

Chaining recursive functions

$T(0,r) = k$ $T(n,r) = k + T(n-1,r) + T(n-1,r+1)$ $T(n,0) = k + T(n-1,0) + T(n-1,1)$ $T(n,1) = k + T(n-1,1) + T(n-1,2)$ $T(n,2) = k + T(n-1,2)$ $T(n,3) = k$ Compact: $T(n,0) = k' + T(n-1,0) + ...
0
votes
1answer
39 views

$T(n) = 2T(n/2) +n\log n$ - Algorithms

According to this http://en.wikipedia.org/wiki/Introduction_to_Algorithms $T(n)=2T(n/2)+n\log n$ is not case 3 of Master Theorem, can someone explain me why? And which case of master theorem it is?
1
vote
3answers
151 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
1
vote
1answer
141 views

Solving the recurrence relation $T(n) = T(n-\sqrt n) + 1$

I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such ...
0
votes
3answers
478 views

Recursive sequence - Convergency and Limit

i just started university so im pretty new to all this new math. My problem is to solve this recursive sequence: $a_{n+1} = a_{n}^3$ with: $a_{0} = \frac{1}{2}$ ...