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

learn more… | top users | synonyms

0
votes
1answer
6 views

Polynomial Multiplication through Toom-Cook into Karatsubas

I'm trying to solve a polynomial multiplication problem recursively through using Toom-Cook (Toom-3) once and Karatsuba (Toom-2) five times, although I'm stuck after the first round of Karatsubas. ...
2
votes
1answer
22 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
2
votes
0answers
31 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
4
votes
3answers
90 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
1
vote
1answer
31 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
0
votes
2answers
89 views

Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
0
votes
1answer
33 views

Recursive definition of the set of odd numbers

Show that the following is another recursive definition of the set ODD (keep in mind you’ll need say something about even numbers too): Rule 1: 1 and 3 are in ODD. Rule 2: If x is in ODD, then so is x ...
0
votes
1answer
34 views

Analyze the following recurrence relation.

I'd like to express the following recurrence relation as the number of multiplications it performs, and then again but this time as the number of additions/subtractions it performs. ...
2
votes
1answer
29 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
1
vote
2answers
45 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
2
votes
1answer
47 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
0
votes
1answer
19 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
0
votes
1answer
63 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
1
vote
1answer
41 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
3
votes
0answers
36 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [closed]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
1
vote
2answers
46 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
-1
votes
0answers
31 views

math formulation of splitting intervals algorithm

So I have this recursion in my mind I am trying to formulate in a sequence fashion for some algorithm problem. So given i , I can tell you where $x_{i}$ along the real line (like the type writer ...
0
votes
1answer
30 views

Turn recursive definition of a function into direct formula

I'm creating a tree diagram, and I'm trying to calculate the amount of white spaces I need at the left side. As you can already see this is done in a program. The formula goes like this: $$ ...
4
votes
5answers
93 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
2
votes
1answer
58 views

Recurrence - using power series

Could you help me in solving this recursion( a closed form ) using power series $\mu(n)=\mu(n−1)k_0+(n−1)\mu(n−2) k_1 \tag 1$, where $k_0,k_1$ are constants $\mu(0)=3,\mu(1)=5$ HINT: We can think ...
0
votes
1answer
23 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
1
vote
1answer
48 views

Infinite series for recurrence

Question 1 If I define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!} \tag 1$ (where $a_n$ are $3\times 3$ constant matrices indexed with n), then can we re-write $\sum_{n \ge 1} a_{n-1} \frac{z^n}{n!} ...
3
votes
2answers
89 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
0
votes
0answers
24 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
0answers
50 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 ...
5
votes
3answers
364 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
7
votes
3answers
228 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$.
0
votes
0answers
24 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 ...
2
votes
1answer
33 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)$$ ...
0
votes
0answers
17 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 ...
3
votes
1answer
196 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
19 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 ...
0
votes
0answers
27 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 ...
1
vote
1answer
29 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
76 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
47 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
17 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
79 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
53 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
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
2answers
45 views
0
votes
2answers
36 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
65 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? ...
0
votes
0answers
22 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
52 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 ...