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

learn more… | top users | synonyms

1
vote
1answer
59 views

A long strip of paper

A strip of paper has $1024$ units in length and one unit wide, divided into 1,024 unit square. The strip is folded repeatedly. The first fold is done such that the right edge coincides with the left. ...
0
votes
1answer
56 views

Pile of $2000$ cards

A pile of cards $2000$ is labeled with integers from $1$ to $2000$, with different integers of different cards. The cards in the pile are not in numerical order. The top card is removed from the pile ...
1
vote
0answers
331 views

Recursive number digits power n sum => is there a limit of unique result numbers found?

Say you have a number xyz and you choose to split it to digits, take a power of each digit to three and summarize them. Some numbers gives same result than the original number, for example: 153 = 1^3 ...
7
votes
3answers
309 views

Error accumulation in an approximating numerical algorithm for $y_n =\int_{0}^{1} \frac{x^n}{x+10} dx $

Consider the problem of calculating the integral $$y_n =\int_{0}^{1} \dfrac{x^n}{x+10} \mathrm{d}x $$ for a positive integer $n$. Observe that $$y_n + 10y_{n-1} = \int_{0}^{1} \dfrac{x^n +10x^{n-1}}{...
1
vote
1answer
89 views

Convergence of Recursive algorithms

In a kind of signal processing problem I faced the following recursive (boot-strap) algorithm: $$R_{k} = R_{k-1} + (y_k-H s_{k-1})*(y_k-H s_{k-1})^T$$ $$s_k = (H^T R_k^{-1} H)^{-1} H^T R_k^{-1} ...
1
vote
1answer
59 views

Using series to produce guess for algorithm analysis

I need to find the upper asymptotic bound for the recursion: $$ T(k) = 2T(k-1)+\frac{1}{k} $$ I was able to determine: The height of this tree is $k-1$. The cost of each level is $\displaystyle{\...
1
vote
0answers
126 views

substitution method for recurrence tree

If one has recurrence function - $$T(k) = 2T(k-1)+ \frac 1k$$ how can one determine the upper and lower bounds? For upper bound, I try use 'substitution method' and drew out recurrence tree, ...
2
votes
2answers
501 views

Using Master's Theorem with $f(n) = \lg^2 (n)$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question: $$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$ I've tried to apply the Master's ...
2
votes
2answers
71 views

Do all recursive fuctions also have a non-recursive version of itself?

Is there any proof that states that any recursive function has to have a non-recursive function that has the same output as the recursive function?
4
votes
1answer
332 views

Computing sums of divisors in $O(\sqrt n)$ time?

I have a sequence: $1,3,5,8,10,14,16,20,23,27,\dots$ I know that the recursive relation is: $$p[i] := p[i-1] + \text{number of factors of $i$}, \quad \text{with $p[1]=1$.}$$ How do I solve this ...
1
vote
1answer
572 views

Sorting Numbers into Groups

I have a list of numbers N1,N2,N3………… The list must be grouped into groups of 3 G1,G2,G3….. The sum of Each Group must be >= X, The sum of Each Group must be <= Y I understand that there may be ...
2
votes
1answer
130 views

Show the following matrix recursion is symmetric

I need to show the following matrix equation is symmetric and I'm not sure where to start: $A_i=\sum_{j_1=1}^{i-2}2(i-j_1-1){i-2 \choose j_1-1}A_{j_1}\Big(\sum_{j_2=1}^{i-j_1-1}{i-j_1-2 \choose j_2-1}...
0
votes
1answer
152 views

Recursive fibonacci algorithm correctnes? [proof by induction]

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction. here is my recursive version of ...
4
votes
2answers
116 views

Filling the plane with a sequence

I am not sure if this is the right stack to ask this question, but since there is a definite fractal dimension to it, I thought I'd give it a go. The problem I am facing is one of calculating an ...
0
votes
1answer
410 views

Solving recursive relations using matrix method.

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in ...
5
votes
1answer
83 views

After $n$ iterations of the continued fraction algorithm, what kind of rational numbers will have terminated?

For a positive real number $r_0$, we have the continued fraction recursive algorithm: \begin{align} &r_n\in\mathbb{Z}\implies\text{terminate the algorithm}\\ &\text{else } r_{n+1} = \frac{1}{...
0
votes
1answer
504 views

Recursive formula for subset sum?

Wikipedia describes an algorithm for the subset sum problem which runs in time $O(2^{\frac{n}{2}})$. It works by dividing the set in half once, computing all the sums in each half (cleverly presorted)...
3
votes
1answer
157 views

Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
2
votes
1answer
233 views

On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$. Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$ We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in ...
0
votes
4answers
1k views

Second-Order, Linear Inhomogeneous Recurrence Relation With Constant Coefficients

How does one solve the general recurrence relation $$s_n=\alpha s_{n-1}+\beta s_{n-2}+\zeta(n)?$$
3
votes
2answers
218 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
1
vote
1answer
122 views

Orange Juice, Milk, or Beer

Suppose that we have $n$ dollars and that each day we buy either orange juice for a dollar, milk for two dollars, or beer for two dollars. If $R_n$ is the number of ways of spending all the money, ...
1
vote
1answer
283 views

$n$-Bit Strings Not Containing $010$

So, I am asked to consider the number of $n$-bit strings that don't contain $010$ by considering the following $m$-leading-zero cases for $m\geq 0$, where $m\in \mathbb{N}$: $1\cdots$ $01\cdots$ $...
0
votes
3answers
323 views

(CHECK) $n$-bit Strings Containing a Pattern

$$\text{$\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}$}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and initial ...
0
votes
1answer
207 views

Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The Schröder numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The Schröder number $...
2
votes
1answer
64 views

help deriving a closed formula for this “magic function”

I'm having trouble coming up with a closed formula for $n$ from the sequence of numbers generated by this function: The following mystery function $M : N \times N \rightarrow N $ is defined by: $$ M(...
1
vote
1answer
52 views

Asymptotic Equivalence of Another Recurrence: [duplicate]

So I have the following recurrence relation: $$f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$$ I already know that: If: $$g(n) = g(n-1) + 1$$ $$g(n) = O(n)$$ If: $$g(n) = g(\lceil n/2\rceil) + 1$$ $$...
5
votes
1answer
183 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
-1
votes
1answer
244 views

How to know when to use Dynamic Programming? [closed]

Given any problem, how do I know whether it is solvable using Dynamic Programming? For example: consider the rod cutting problem. Now, how do I know whether dynamic programming will give me an optimal ...
4
votes
1answer
111 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
6
votes
0answers
161 views

Generating Functions, Recursive Polynomials

At the CMFT international conference in Turkey (2009), the following open problem was given: Show that $$p_n(x):=\sum_{k=0}^n \frac{(n-k)^k}{k!}x^{n-k}$$ has only real simple zeros for every $n$. ...
1
vote
2answers
151 views

Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a ...
0
votes
3answers
2k views

Show that the limit exists and find it's value? [duplicate]

The Fibonacci series defined recursively by $x(1) = 1, x(2) = 2$ and $x(n+1) = x(n) + x(n-1)$ Find$$\lim_{n\rightarrow\infty}\frac{x(n+1)}{x(n)}$$
2
votes
0answers
65 views

Difference Sets

suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct. We calculate the differences as: $$d=p_i-p_j\mod ...
1
vote
2answers
86 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
1
vote
3answers
71 views

Recursively Defined Functions

I am taking a summer class in discrete math and have done very well up till now. I am nervous because I have reviewed the lecture slides and practice problems but I still don't really understand what ...
2
votes
1answer
669 views

numerically evaluate a continued fraction

I am looking at a continued fraction of the form $$ F_n = \cfrac{1}{1+\cfrac{p_1}{1+\cfrac{p_2}{1+\cfrac{p_3}{1+\ldots}}}} $$ where $p_n$ is a function I know. For simplicity I just take it to $p_n=n$ ...
0
votes
1answer
80 views

Finding in a string S if is possible to create a set with perfect cubes or perfect squares with elements of S.

You have a sequence $S[1...n]$ with $n$ digits(0 to 9) and you wanna know if its possible break then in perfect square or perfect cube. For example, if $S = 1252714481644$, then the answer is $YES$ ...
6
votes
4answers
234 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
4
votes
3answers
101 views

Recurrence relation not working as expected

I was dealing with the following recursive formula which had three constants ($k_1, k_2, k_3$) where $x$ would always be an integer: $$ f(x) = \begin{cases} 0 & if x = 1\\ k_1f(x-1) + k_2x + k_3 ...
0
votes
4answers
90 views

Solving a simple ${\cal O}(N\log N)$ recursive equation.

A recursive divide and conquer algorithm runs for input size $N$ in $T(N)$ time where $$ \begin{align} T(1)&={\cal O}(1) \\ T(N)&={\cal O}(1)+2T(N/2)+{\cal O}(N) \\ \...
2
votes
1answer
71 views

Sum count algorithm name

I want to find out what this algorithm is called ...
0
votes
2answers
130 views

Recursive function into non-recursive

I have to express $a_n$ in terms of $n$. How do I convert this recursive function into a non-recursive one? Is there any methodology to follow in order to do the same with any recursively defined ...
2
votes
0answers
168 views

Subtrees of a tree

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K. for example: If ...
2
votes
3answers
463 views

What does 'i-th' mean?

I have seen a problem set for the tower of hanoi algorithm that states: Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is ...
1
vote
1answer
1k views

Master Theorem change of variables with root other than 2

I'm working on this: $$T(n) = 12T(n^{1/3}) + \log(n)^{2}$$ Using change of variables, and substituting $m = \log n$, I get as far as: $$S(m) = 12S(m/3) + m^{2}$$ I see how a square root would work ...
0
votes
1answer
513 views

Recursive Function for Pyramid-Scheme

consider a group which has 1 user. each month, every user can bring another user to join the group. the user that has been joined for 3 months, should leave the group. calculate the total membership ...
-1
votes
1answer
95 views

recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n)=aT(n/b)+f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master theorem: ...
2
votes
1answer
111 views

Application Church-Turing thesis

I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would ...
5
votes
2answers
474 views

Has anything useful come from Ackermann's Function?

Here is the function: if (m == 0) return n + 1; else if (n == 0) return A(m-1, 1); else return A(m-1, A(m, n-1)); This seems like an interesting ...