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

learn more… | top users | synonyms

1
vote
1answer
56 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
84 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
78 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
1answer
48 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
52 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
96 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
1answer
104 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 ...
1
vote
2answers
32 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
2answers
66 views

Towers of Hanoi recurrence relation

How would I do this recurrence relation?
0
votes
2answers
49 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 ...
2
votes
1answer
69 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,& ...
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? ...
1
vote
1answer
34 views
0
votes
0answers
59 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 ...
0
votes
1answer
43 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
33 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 ...
-3
votes
1answer
55 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
74 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
56 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) ≤ ...
1
vote
1answer
74 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 ...
1
vote
1answer
77 views

Karatsuba Method

For polynomials $f(x)$, $g(x)$ of degree $d = 2^{r-1}-1$, how do I check that multiplying $f(x)$ and $g(x)$ by the Karatsuba method requires $3^{r-1}$ multiplications in the field $F$?
2
votes
1answer
24 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
84 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.
1
vote
2answers
45 views

Relation between series and equations

There is following quotes from wiki on Plastic number: The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$. And 2nd is that ...
0
votes
1answer
58 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 ...
-4
votes
1answer
48 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}) ...
8
votes
6answers
718 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)
-1
votes
1answer
52 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} ...
1
vote
0answers
53 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
49 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?
0
votes
0answers
46 views

How can I find the height of the Recursion Tree?

How do I determine the height of a Recursion tree? For example for the recursion $T(n) = 3T(\frac{2n}{3}) + O(1) $. Could you give me a hint?
1
vote
1answer
361 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
1answer
25 views

How to calculate rental income of an appreciating property?

I'm trying to calculate the total rental income I might receive over 25 years. The rent is 5% of the property value, which is initially £300k. If the property itself increases in value by 3% per year, ...
0
votes
1answer
44 views

how to write a recursive definition

so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to ...
1
vote
1answer
81 views

Combinatorial Proof of Identity

How do I build a combinatorial proof of the following recursion: $$\binom {n}{k} = (k+1)\binom {n-1}{k}+(n-k)\binom {n-1}{k-1}$$ I'm having really big difficulties in finding the right way to ...
3
votes
1answer
44 views

$n$th term of a recursive formula

I have a formula $$ 1 + px + \dfrac{p(p-1)}{1*2}x^2 + \dfrac{p(p-1)(p-2)}{1*2*3} x^3 $$ can someone please tell me what the formula is for the $n$th term of this recursive definition ? Do I have to do ...
2
votes
0answers
55 views

Proof relating to Euclidian Algorithm

The question is as follows: (1): Let m and n be positive integers with n < m and let r be the remainder when m is divided by n. Prove that $$r < \frac m2$$ (2): The Euclidean Algorithm for ...
1
vote
0answers
73 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
2
votes
0answers
43 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
1
vote
2answers
79 views

Solving this recurrence relation

Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction $$ {\rm ...
3
votes
0answers
92 views

What is this method of dividing a plane called?

I have an idea of a method for recursively dividing a plane, and as I'd like to do more research about this algorithm and the set of points that it produces, I'd like to know what it's formally known ...
1
vote
1answer
270 views

Cyclic tower of hanoi problem [duplicate]

If I have 3 rods in a circle and it is allowed to move the disks only in the clockwise direction. How many moves is necessary to move n disks from first rod to the third rod?
1
vote
2answers
54 views

Calculate a recursive equation in terms of theta

I am struggling with the following equation for one week! Please help me solve it. $$T(n)=T(\frac{n}{2})+\frac{n}{logn}$$ So far, I have come to the equation $T(n)=\Sigma \frac{2^x}{x}$
0
votes
1answer
125 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
2
votes
1answer
371 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
1
vote
1answer
63 views

Transfer a program into a logarithm formula

I have been thinking what is the math formula for the piece of code I wrote below. Assume there are B, D and F three positive integers, and D is smaller than F. Given D and F, the value of B would be ...
2
votes
0answers
33 views

Recursive and Recusively enumerable

{1^n | n finite integer and >1}, is this language recursive? I'm not sure how to prove that a language is recursive, I only know that there should be a TM that accepts any finite input and then ...
0
votes
1answer
37 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
1
vote
1answer
37 views

What is the link between the quotient and the Bézout coefficients in the Extended Euclidean Algorithm?

Here is an image from the wikipedia page of the EEA for working out the Bézout coefficients for 240·sk + 46·tk = rk where rk = GCD(240,183): What I am trying to work out is what si and ti ...
2
votes
1answer
158 views

The Matrix Inversion Lemma: the General Case

I find it is hard to understand the application senario of the Matrix Inversion Lemma in non-special cases. Suppose I already computed $A^{-1}$ and want to find $\left(A+UCV \right)^{-1}$. The Matrix ...