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

learn more… | top users | synonyms

5
votes
0answers
141 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$. ...
4
votes
0answers
111 views

Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?

The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=0$. Therefore, $z_1=c$, $z_2=c^2+c$, $z_3=c^4+2c^3+c^2+c$, etc. I have a function ...
4
votes
0answers
587 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
4
votes
0answers
187 views

Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?

For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $ \small z^2 $ by ...
3
votes
0answers
82 views

Algorithm for Converting Rational Into Surreal Number

I'm writing a library in Haskell that represents the class of surreal numbers, which like many things can be read about here. I've run into a problem in converting between other classes of numbers ...
3
votes
0answers
41 views

What's the next “recursion” here?

Plotting a single 3d helix is x = cos(t); y = sin(t); z = t; From this equation: x = [R + a cos(\omega t)] cos t y = [R + a cos(\omega t)] sin t z = h t + a sin(omega t) Comes the awesome ...
3
votes
0answers
94 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 ...
3
votes
0answers
259 views

Question about recursive defined functions.

This question is about counting functions. With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ...
2
votes
0answers
17 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
2
votes
0answers
39 views

Solving this recurrence relation representing constant-power loads on a resistive cable

Given the following: $$\begin{align} v_n&=v_{n-1}-r\sum_{i=n}^m \frac p{v_i}\\ v_0&=V \end{align}$$ where: $$\begin{align} m\ge n\ge 0\;&:\;m,\,n\in\mathbb {N_0}\\ ...
2
votes
0answers
116 views

How to find a enclosed envelope with maximum points among a cloud of spheres? [ Concave Hull ]

I have a questions regarding the selection of the outer points (i.e. sphere center), among a collection of many spheres in 2D/3D space. The outer points is that when all of these points are ...
2
votes
0answers
46 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
0answers
96 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...
2
votes
0answers
101 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. ...
2
votes
0answers
58 views

Proof relating to Euclidean 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 ...
2
votes
0answers
44 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$ ...
2
votes
0answers
34 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 ...
2
votes
0answers
188 views

Algorithm for reversion of power series?

Given a function $f(x)$ of the form: $$f(x) = x/(a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4+a_5x^5+...a_nx^n)$$ Let $A$ be an arbitrary (any) infinite lower triangular matrix with ones in the diagonal: $$A ...
2
votes
0answers
86 views

Interesting Recursive Continued Fraction Limit

I was messing around with recursive functions the other day and came up with something that could be interesting: Definition of $\bar{\Xi}(n)$:\ Let $\Xi ...
2
votes
0answers
62 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 ...
2
votes
0answers
151 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
0answers
138 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
107 views

Is there a closed form for this recurrence?

Given $$ E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases} $$ I wonder is there ...
2
votes
0answers
79 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
2
votes
0answers
204 views

Who invented the breadth-first permutation algorithm?

My initial problem was solved here. It is about enumerating all n-tuples of a permutation in a specific order. The solution algorithm is very simple and I'm sure has been used before. However, I did ...
2
votes
0answers
79 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...
2
votes
0answers
218 views

google page rank algorithm with range of values

According to the wikipedia article, the iterative google page rank algorithm is defined as follows: Can this be modified to include a range of values, not just binary, and would it look something ...
2
votes
0answers
134 views

Help on Generating function - Analysis of Median of three - Quick Select

I am trying to find out the average case analysis of median of 3 - quick select. The recurrence relation is \begin{equation} C_{n,j} = 1 + \sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} ...
2
votes
0answers
197 views

How to solve the recursive relation in Kalman filter?

I was wondering how to solve the Kalman filter's recursive equation (also see the appendix at the end of this post) for the estimated state $\hat{\textbf{x}}_{n|n}$ at time $n$, over discrete times ...
1
vote
0answers
45 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, ...
1
vote
0answers
21 views

FFT procedure for evaluationg a polynomial at $N$ Fourier points

The following is the recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points. Algorithm (FFT - fast Fourier transform). Input arguments. $ \ ...
1
vote
0answers
20 views

Sources and sinks for parabolic PDE algorithm

I am given a very basic fortran program (View here) and asked 1st to investigate its accuracy and stability, for various values of $ \Delta t $ and lattice spacings. The program is an implementation ...
1
vote
0answers
69 views

Coppersmith-Winograd algorithm

I'm interested in algorithms to compute matrix multiplications. Is the Coppersmith-Winograd algorithm similar to the Strassen algorithm ? I have two other questions: 1) Are the multiplications done ...
1
vote
0answers
20 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
1
vote
0answers
29 views

Runtime of recursive algorithm - Master's Theorem

I wrote a computer program that solves a question, and I am interested in knowing what is the runtime. My aim is for $O(\log n)$, and I'd like someone more experienced (and smarter?) to review my ...
1
vote
0answers
65 views

Greek cross fractal

I need some code to generate a Greek cross fractal. Example: It must be made of increasingly smaller panels, but the panels may not overlap with previous panels. Does anyone know where I might ...
1
vote
0answers
19 views
1
vote
0answers
27 views

algorithm related to dyadic decomposition

Starting from an integer $n >0$, iterate the two operations of substracting one and dividing by $2$ (when the number is even) until $1$ is reached. Thus when the number is odd we can only substract ...
1
vote
0answers
43 views

Using FFT to compute DFT of a polynomial

i currently studying about FFT and DFT and we were given simple question: Use the recursive FFT to compute the DFT of this polynomial of '3' degree: $$-1\:+\:4x\:+\:3x^2$$. So, i go to this ...
1
vote
0answers
26 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
0answers
60 views

Help me generalize what this divisor transform does.

I have an algorithm which takes as input the series expansion of: $$\frac{-(1 + ax(-2 + x + ax))}{-1 + ax} \tag 1$$ or expressed differently: ...
1
vote
0answers
89 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} ...
1
vote
0answers
30 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 ...
1
vote
0answers
38 views

Finding the explicit form of the recursive function $P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor$

I'm trying to find the explicit form of the recursive function $$P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor\;.$$ First, let me explain what this ...
1
vote
0answers
42 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ ...
1
vote
0answers
35 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
1
vote
0answers
83 views

Using a Recursion Tree to solve the recurrence $T(n) = \sqrt n T(\frac{n}{2}) + 10n$?

I am attempting to solve the above recurence by giving tight $\Theta$ bounds. Assume that the logs here are all base 2! To solve a recursion tree as far as I understand, I need two things. The ...
1
vote
0answers
80 views

Algorithms recurrence equation using unwinding / substitution

This is homework for introduction to Algorithms this is what I have below. (25 pts) Use the direct unwinding to prove that the recurrence equation T(n)= 2T(n/2)+ nlogn has a lower bound of ...
1
vote
0answers
36 views

Divisible 4 for every different number?

My formula is for ABC 3 digits number; 100A + x*B + y*C. What should coefficient of B and C be for everytime different result for different number? (Result number ) mod 4 has to be zero. For ...
1
vote
0answers
54 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 ...