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

learn more… | top users | synonyms

5
votes
0answers
96 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
153 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
29 views

Four for loops in Matlab — optimize for speed

Let $s$ be a constant integer. I am computing a four dimensional matrix $A$ of size $(s+1)^4$ with entries in $[0,1]$. For this computation we use a three dimensional matrix $B$ of size $(s+1)^3$ with ...
3
votes
0answers
79 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
209 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
267 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
42 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
20 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
21 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
73 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
94 views

Is there any efficient algoritm to solve the given $2$ equations?

My equations are as follows: $$\alpha(A,B)=\frac{\sum_{n=1}^\infty P_0[T=n|A,B]\left(nK_0-s_n\right)}{\sum_{n=1}^\infty P_1[T=n|A,B]r_n-\sum_{n=1}^\infty P_0[T=n|A,B]s_n}$$ ...
2
votes
0answers
125 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
96 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) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
2
votes
0answers
94 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
96 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
72 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
136 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
127 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
157 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 ...
2
votes
0answers
244 views

Optimal division sequences for divide-and-conquer algorithms

Say we have a discrete data set of some size, and we can use a recursive divide-and-conquer algorithm to process the data in some way (an FFT for example). The naive solution is, say, $n^2$ in ...
1
vote
0answers
39 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
58 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
16 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
16 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
38 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
104 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
130 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
41 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
113 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
165 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
73 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
62 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
88 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
60 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
23 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 ...
1
vote
0answers
61 views

Confusion related to time complexity of fast Fourier transform

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT. It says that lets say I have a polynomial of ...
1
vote
0answers
154 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 ...
1
vote
0answers
73 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 ...
1
vote
0answers
145 views

Panjer Recursion and Expectation

Given a Panjer Recursion set up, with the usual properties, and supposing now that $N$ has a Poisson distribution with mean $\lambda$. How can we derive a recursion for $E(S^k)$ where $S$ be the ...
0
votes
0answers
27 views

How can I find the height of the Recursion Tree?

How do I determine the height of a Recursion tree? For example for the recursion $T(n) = 3T(\frac{2n}{3}) + O(1) $. Could you give me a hint?
0
votes
0answers
23 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
0
votes
0answers
5 views

How to formally describe indirect partial derivatives with two paths

Assume I have two functions like this: $y = \frac{1}{2}(o-x)^2\\o = kx$ Now, I want to calculate $\frac{\partial y}{\partial x}$ using the chain rule, i.e. like this: $\frac{\partial y}{\partial x} ...
0
votes
0answers
48 views

Inventory Control using Dynamic Programming

I am trying to solve a traditional inventory control stochastic dynamic programming problem where \begin{align} x_{k+1} &= x_k + u_k - w_k\\ w_{N-1} &= \begin{cases} 0 &\text{w.p. } ...
0
votes
0answers
27 views

How to define this f(n) (something about recursion)?

Consider this: $$best(n)=\begin{cases}1 & \text n=1,\\2*best(n-i)+2^i-1 & \text otherwise,1<=i<n\end{cases}$$ That is, when $n>1$, for each $i$ among $[1,n)$, there must be at least ...
0
votes
0answers
43 views

Why can I not generalize O(n^log5) for squaring matrice of size n

I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
0
votes
0answers
67 views

Find all possible paths in a Matrix

I'm looking for algorithms to find all paths in a 4 x 4 matrix. The rules are as follows You can move in any direction (up, down, left, right, and diagonally) The next square in the path must be a ...
0
votes
0answers
24 views

Algorithms Analysis: Double Recursion and how to Analyze?

This is quite a simple question, but maybe not so simple to think about. What if I have an algorithm which has "stacked" recursion, such as this? Func(n): ...
0
votes
0answers
33 views

Tight bounds for the number “2 in a hexagon” wanted (Steinhaus-Moser-Notation)

The Steinhaus-Moser-function is defined in the following way : $$M(n,1,3) = n^n$$ $$M(n,1,p+1) = M(n,n,p)$$ for all $p\ge3$ $$M(n,m+1,p) = M(M(n,1,p),m,p)$$ for all $p\ge3$ and $m\ge1$ The ...
0
votes
0answers
47 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.
0
votes
0answers
52 views

Algorithm for reversion of power series?

Is this an algorithm for power series reversion? As input I give the alternating reciprocals of the factorial numbers: ...