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

learn more… | top users | synonyms

4
votes
2answers
115 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
388 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
80 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} = ...
0
votes
1answer
487 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 ...
3
votes
1answer
153 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
227 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
212 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
263 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
309 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 ...
0
votes
1answer
202 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
63 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: $$ ...
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
181 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
243 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
110 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
159 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
150 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
63 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
83 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
635 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
77 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
233 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
99 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
89 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
69 views

Sum count algorithm name

I want to find out what this algorithm is called ...
0
votes
2answers
126 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
167 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
435 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
488 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
93 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
469 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 ...
2
votes
1answer
289 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
0
votes
1answer
164 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
1
vote
3answers
121 views

Solving the recurrence relation $T(n) = 2T(n^\frac{1}{2}) + c$

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$? I've ...
2
votes
2answers
1k views

Recurrence Relation for Strassen

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} ...
7
votes
1answer
160 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
1
vote
1answer
93 views

Solving recurrenc using recurrence tree method.

I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$. I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
8
votes
3answers
764 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)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I ...
0
votes
2answers
69 views

Equation of a curve whose difference in ordinate values form an arithmetic sequence

I have the following recurrence equation that I have obtained while trying to solve a problem:- $$T(0) = 1$$ $$T(n) = T(n-1) + 9n - 8: n \ge 1$$ The values of $T(n)$ for $n = 0,1,2,... $ are as ...
1
vote
1answer
430 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
3
votes
2answers
614 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
0
votes
0answers
522 views

How to find integer solutions of an equation using approximation methods?

If I have a function called $f(x)$ that have several roots, integers and not integers. How can I find just the integer ones by approximations methods? A simple example would be ...
2
votes
1answer
199 views

Quadratic Forms and Newton's Method

Consider the function $f(x,y) = 5x^2 + 5y^2 -xy -11x +11y +11$. Consider applying Newton's Method for minimizing $f$. How many iterations are needed to reach the global minimum point? Why should ...
1
vote
1answer
105 views

How do I determine if two of my software's representation of algebraic numbers are equal?

I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, ...