Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,375 questions
2
votes
0
answers
37
views
Kolakoski sequence $K(1,3)$ recursive $K(1,2)$ not...
Why does the Kolakoski sequence $K(1,3)$ admit a precise recursive block-pillar structure where
$$B_{n+1} = G(B_n, 1) = B_n \cdot P_n \cdot B_n$$
when no such simple construction exists for $K(1,2)$?
...
2
votes
0
answers
40
views
The growth rate of a recursively defined function
Imagine a function where you know how to get from $f(n)$ to $f(n-1)$ and from $f(2n)$ to $f(n)$. How many steps would it take to get to $f(1)$? I am not talking about the optimal route but rather if $...
- 29
0
votes
1
answer
101
views
Finding order of time complexity for program finding the $m$-subsets of an $n$-set.
For the code here, the analysis for the order-of-time complexity is as follows:
For the purpose of finding the time-complexity of the above program; the program statements of concern are:
...
- 4,908
0
votes
1
answer
58
views
Redistributing points along a set of points (Stroke)
I'm currently facing the following problem: I want to write an algorithm that, given as input a list of points (representing a path/stroke/curve), and a target $distance$ it creates a new stroke that ...
- 405
2
votes
2
answers
68
views
Minimum distance decoding
I have been researching decoding methods for Reed–Muller codes and am currently reviewing a recursive decoding approach proposed by Ilya Dumer in his paper “Recursive Decoding and Its Performance for ...
0
votes
1
answer
73
views
Algorithm to expand arbitrary partitions
Suppose you have an expression like:
$$
(a + b + c + d)(e + f + g)(h + i)
$$
Is there a method to expand this expression that does not involve multiplying only two groups at a time? Some way to ...
- 41
0
votes
1
answer
72
views
Recursive to explicit/closed form [duplicate]
A similar question has been asked before but I haven't seen an answer to this specific one after looking for so long.
I have a recursive function where:
$P(2) = 1$
For $n ≥ 3$, $P(n) = (n-2)P(n-1) + ...
- 69
0
votes
0
answers
43
views
Solve Recurrence Relation with Master theorem Case 3
I need your help with the following problem:
I’m supposed to find a simple function $ g(n) $ for the recurrence relation
$ T(n) = 9 \cdot T\left( \lceil \frac{n}{4} \rceil \right) + 3^n $
with the ...
- 43
0
votes
0
answers
75
views
Recursive system identification initialization (continuous-time model)
I have a doubt concerning recursive system identification. I have seen that in many occasions we have a data set $u(t)=[u(1)\, u(2) \, \dots]$. When the first couple of data $y(t)$ and $u(t)$ arrives,...
- 131
0
votes
0
answers
17
views
Convergence of $ \vec{x_{n+1}} = A^{-1} f(\vec{x_{n}},\vec{y_{n}}), \:\:\: \vec{y_{n+1}} = A^{-1} g(\vec{x_{n}},\vec{y_{n}}) $
I have two systems
$$ A \vec{x} = f(\vec{x}, \vec{y}), \:\:\: A \vec{y} = g(\vec{x}, \vec{y}) $$
Both have same constant, square matrix $A$. I implemented an iterative algorithm with an initial value ...
- 5,019
3
votes
2
answers
115
views
Asymptotic equivalent of sequence defined by a recursion relation.
For the study of a termination speed of a recursive algorithm of mine, I would like to have more precise result on the following sequence:
$$0< a_0 = a< 4 \qquad \text{and} \qquad a_{k+1} = \...
- 5,389
0
votes
0
answers
35
views
Correctness of recursive sorting algorithm through induction
Hi I need help to prove the correctness of a recursive algorithm.
It works like this, it takes an input array A with the size of the array being a power of 4.
The algorithm is defined like this:
sort(...
1
vote
1
answer
186
views
Explain how to find this formula from the recursion in this paper
I am trying to understand how to find this formula, which seems straight forward, but I am missing something.
In page 20 of this paper (or thesis):
https://egrove.olemiss.edu/cgi/viewcontent.cgi?...
- 1,042
0
votes
0
answers
36
views
Strict bound for recurrence formula
Given the recurrence $$T(n) = (2k - 1)T(\frac{n}{k})+2^kn$$ I need to show (or disprove) that for every $\epsilon>0$ there exists a $k$ such that $T(n)=o(n^{1+\epsilon})$.
So far, I've been able to ...
- 461
0
votes
1
answer
51
views
solve a recursion formula using a generating function
I have the following formula for a vector $v_n= \ ^t(a_n, b_n)\in \mathbb R^2$ :
$v_n= Av_{n-1}+ Bv_{n-2}$ for two given matrices $A$ and $B$ in $M_2(\mathbb R)$, and we are given $v_1$ and $v_2$ of ...
- 1,042