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

learn more… | top users | synonyms

5
votes
0answers
121 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
171 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
39 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
87 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
248 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 ...
3
votes
0answers
394 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 ...
2
votes
0answers
35 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
33 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=c$. Therefore, $z_1=c^2+c$, $z_2=c^4+2c^3+c^2+c$, etc. I have a function $f(n,x)$ ...
2
votes
0answers
68 views

Local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
2
votes
0answers
85 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
50 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 ...
2
votes
0answers
37 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
30 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
142 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
81 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
57 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
141 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
123 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
103 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
75 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
164 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
129 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
181 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
25 views

What Is The Next Best Ingredient?

I am building a program that allows users to optimize their grocery shopping so they can make the most recipes using the fewest ingredients. One of the features of this program is a function I’m ...
1
vote
0answers
56 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
49 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
24 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
31 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
33 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
32 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
42 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
53 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
34 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
52 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 ...
1
vote
0answers
48 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 ...
1
vote
0answers
49 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) + ...
1
vote
0answers
67 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) = ...
1
vote
0answers
25 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
1
vote
0answers
23 views

Is there a method to calculate Mahalanobis distance incrementally?

By incrementally (or recursively) I mean to update the pool/group of values/vectors as soon as more vectors are available without having to recompute the entire covariance and inverse matrices. I ...
1
vote
0answers
52 views

Is undecidability of arithmetic a corollary of Tarski undefinability theorem?

Arithmetic is undecidable, in other words the set of Godel numbers of theorems of arithmetic is not recursive, and so there is no algorithm/ recursive function to decide if a statement is provable or ...
1
vote
0answers
150 views

Sequential Algorithm to generate Fractal (Koch's snowflake)

As part of an assignment I had developed a sequential algorithm to generate a Koch's snowflake. Algorithm I have encountered so far have been recursive and iterations generate closer approximations. ...
1
vote
0answers
131 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
1
vote
0answers
49 views

How to derive recursive equation for expected discounted utility function?

I am trying to mathematically represent expected discounted utilities when the length of a lifetime is uncertain. $V_0$ is the expected discounted utility at $t=0$ and can be represented as such: ...
1
vote
0answers
210 views

Help with find recurrence relation running time.

Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. ...
1
vote
0answers
220 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 ...
1
vote
0answers
88 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, ...
1
vote
0answers
66 views

How to deduce the results of response time by this trajectory approach?

First, we denote this: And And we get this right property( $last_i$ means the last node on $τ_i$): And: $Smin_i^h$ = $\sum_{h'=first_i}^{h-1} ({C_i^{h'} + L_{max})}$ $Smax_i^h$ = ...
1
vote
0answers
117 views

Non overlapping areas algorithm

One of my fellow members on stackoverflow has posted a question thread which concerns how to write a mathematical equation to calculate the exposed areas of a window from a group of windows (like on ...
1
vote
0answers
68 views

Solving Recursive Equations: How to transform the domain in such cases?

I understand that a widely-used recursive equation for the Binary Search is as follows: $$ \begin{align} T(1) &= 1\\ T(n) &= T(\tfrac{n}{2}) + 1, \quad n>1 \end{align} $$ In order to solve ...
1
vote
0answers
29 views

Algorithm for approaching zero delta.

I'm working on translating an old program for a gas-mixing furnace, and I have a logic problem that I believe I need help on the math with. I have the specimen temperature ($T$), a variable called ...