Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,070
questions
0
votes
0answers
15 views
Self adjusting numerical integration precision
I've written a program to numerically calculate the area under a curve for a given interval and want to be able to give a precision goal.
Let $f: [a, b] \rightarrow \mathbb{R}$ with $a,b \in \mathbb{...
1
vote
0answers
25 views
A random sequence converging to $e$ [duplicate]
Choose a random number between 0 and 1. Add it to 0. Choose another random number between 0 and 1 and add it to your previous sum. If your sum exceeds 1, stop, otherwise continue the same process. ...
0
votes
0answers
12 views
Recurrence Relation jumping forward and backwards between bounds of 0 and m
Question
What I have gotten so far is as follows:
$$q_{m,k} = q_{m,k-1}a_{n-1}$$
for $2|k$, otherwise it is $$q_{m,k} = q_{m,k-1} (m - a_{k-1})$$
Is there any way to make this into one recurrence ...
8
votes
1answer
164 views
How to utilize the special feature of this recursive problem to reduce computational complexity?
Assume
$A$ is a $n \times n$ matrix of non-negative numbers.
$A_i$ is the $i$-th row of $A$.
$(a_1, \ldots, a_n)$ and $(b_1, \ldots, b_n)$ belong to $\mathbb R_+^n$.
$I_0 = \{1, \ldots, n\}$.
$X= [...
1
vote
1answer
39 views
How to calculate the following variance in a recursive way
Suppose we need to divide people into two groups A and B, the first person will be assigned to either of the group with probability $0.5$, from the second person, the assignment will be done based on ...
0
votes
0answers
8 views
Recursive function / conditional asymptotics
Let $t(n):=t(\lfloor \frac{n}{2} \rfloor)+t(\lceil \frac{n}{2} \rceil)+c⋅n$ is $O(n ⋅log n)$
So obviously this is the merge-sort algorithm, it is demanded that we show t(n)∈O(n⋅logn)
that by showing
...
4
votes
1answer
106 views
Any advantages of using Gödel universal functions in proving unsolvability?
Let $U$ be a universal function for the class of computable functions of one variable. This means that $U:N\times N\to N$ is a computable (partial) function and for every computable (partial) function ...
5
votes
1answer
47 views
Question about unclear definition of Ackermann-Péter function in Stanford Encyclopedia of Philosophy
I'm reading Recursive Functions at Stanford Encyclopedia of Philosophy (section 1.4). The following paragraph defines function β which is then used to define variant of Ackermann-Péter function:
What ...
0
votes
0answers
19 views
Partitioning a log with minimum cost
I am struggling with a problem that requires me to find a general pattern and come up with a solving algorithm. The problem goes on like this:
You are given a wood log of length L and a number n that ...
0
votes
0answers
5 views
Implementing L-Systems for conversion (instead of drawing): Extending the Hilbert space filling curve
I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
-2
votes
1answer
23 views
Recursive Algorithm Question [closed]
I am having a difficult time figuring out where to start this problem. Any input on where to start would be greatly appreciated.
Consider the recursive algorithm, which operates on a sequence of ...
0
votes
1answer
24 views
Master theorem proof about relationships $T(n)=aT(n/b)+f(n)$
I am reading the proof of Master theorem from Cornell University lectures:
https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/mm-proof.pdf
I am having problem in this step:
$$n^{...
0
votes
1answer
13 views
Minimum cost in a 2D matrix
In my last interview, I was asked a question for which optimal approach I am still not able to figure out.
Given a 2D matrix, with n rows and ...
0
votes
0answers
9 views
What's the derivative of a recursive function $ H_{t} = tanh(Wh * H_{t-1})$ with the product rule involved
I'm writing my own recurrent neural network and it's known to use backpropagation through time. In this, I have a weight $ Wh $, which gets used multiple times in a funtion $ H_{t} $ like in this ...
0
votes
2answers
47 views
Is there any way I can make an explicit formula for the sequance $a_n=x+ya_{n-1}$?
Let $a_n$ be a sequence defined by recursion: $a_n=x+ya_{n-1}, a_1=k$. For example, if $(x,y)=(3,5)$, then the sequence would go
$$a=\{k,\space 3+5k,\space 3+5(3+5k),\space ...\}$$
Is there an ...
0
votes
1answer
19 views
Solving recursive relation
I am trying to solve the following recursive relation
$$K_{2i-2}=\frac{a+K_{2i}}{1+aK_{2i}}\quad;\quad K_{2N}=0$$
and $i=1,\cdots,N$
I want to find the solution for $K_{2i}$.
I believe that this ...
0
votes
1answer
51 views
Why does this algorithm behave linearly when theoretically it should be logarithmic?
I have the following algorithm:
...
4
votes
1answer
74 views
Maximum number of iterations of a simple algorithm
Suppose there is a 0-1 string of length n. We can perform the following operation on the string:
We can choose two zeros and invert the subsequence between them. The inversion includes the two zeros ...
0
votes
2answers
43 views
Harmonic series in the form of $ \sum_{i=0}^{n-1} \frac{1}{n-i} $
I am searching for a solution for a recurrence which ends up in this form:
$$\sum_{j=0}^{\log{n}-1}\frac{1}{\log{n}-j} $$
After substituting $m = logn$ the next step I can find is:
$$\sum_{j=0}^{m-1}\...
2
votes
1answer
48 views
Solve the recurrence: $T(n)= 4T(\frac{n}{2} )+\frac{n^2}{\log n}$
I have been trying to solve the sequence
$T(n)= 4T(\frac{n}{2} )+\frac{n^2}{\log n},$
$T(1)=1$
after calculations, I came to this
$4^k Τ(\frac{n}{2^k})+ \sum_{i=0}^{k-1} \frac{n^2}{log\...
0
votes
1answer
29 views
(Calculus) Solving a geometric series word problem
I’m struggling with understanding how to solve part B of the following problem:
Consider an outdoor pool initially filled with 20,000 gallons of water. Each day, 4% of the water in the pool ...
0
votes
0answers
37 views
find the upper and lower bound of recursive function
I need you to answer this for me:
Give an upper and lower bound to this recursive function.
$$T(h) = T\left(n^{2/3}\right) +20$$
I tried the iterative method and got stuck.
is it possible to ...
1
vote
0answers
35 views
o($n \log n$) algorithm for a noncrossing matching in plane
I am thinking about the algorithm for the following well-known mathematical problem.
$n$ red points and $n$ blue points in the plane in general position are given.
Find the matching $\{r_1, b_1\}, \...
1
vote
3answers
139 views
Recurrence relation with python. [closed]
How to find the terminating value of the continued fractions
$$
S=3-\cfrac2{3-\cfrac2{3-\cfrac2{\ddots}}}
$$
by writing a recurrence relation in Python? (Start from any guess value other than 1.)
0
votes
0answers
31 views
Find a recursive formula for $a_n$, $n ≥ 2$, in terms of $a_{n−1}$ and $a_{n−2}$, where $a_0 = 0, a_1 = 1$
Find a recursive formula for $a_n$, $n\ge 2$, in terms of $a_{n-1}$ and $a_{n-2}$, where $a_0=0$, $a_1=1$, $a_2=-1$.
The power series is
$$\sum\frac{(-1)^{n-1}}{(n-1)!}$$
And can anyone help with ...
0
votes
1answer
31 views
Dynamic Programming Cheapest Train Ride Question
I am struggling with the below dynamic programming practice problem and I am hoping someone can help. The problem states:
"You want to go from station 1 to station n by rail. The train fare from ...
0
votes
0answers
30 views
Expected size of a set with iterative probabilistic growth
We exhaustively compare every item in set $A$ to the items in set $B$, where $A\cap B=\emptyset$, to look for matches.
We repeat this across iterations, where at every iteration, $|A|=n\gt 0$. At ...
1
vote
1answer
32 views
How many ways are there to choose k from n such that the longest consecutive block chosen is j things long?
Denote the number of $\binom{n}{k}$ such that the longest consecutive block of things chosen is exactly $j$ things long as ${\binom{n}{k}}_{j}$, where $j\leq k \leq n$; the goal is to derive a general ...
3
votes
1answer
74 views
A question about the plastic number
The plastic number is well known to be the limiting ratio of the Padovan sequence (OEIS A000931), to wit,
$$
P_n=P_{n-2}+P_{n-3}\\
\lim_{n\to \infty} \frac{P_{n+1}}{P_n}=p
$$
However, it is also the ...
0
votes
0answers
22 views
Algorithm for auto convolution
I have a question, since we have a divide and conquer algorithm for calculate normal convolution sequence in n^log(3) [n power log 3 base 2] , i thought maybe symmetric feature in auto-convolution can ...
1
vote
2answers
47 views
How to obtain a formula for $f(z)$ given this recurrence
I am trying to figure out how to derive a formula for $f(z)$ that is a function of $z$ and maybe $k \in \mathbb{N}$:
$$
f(z) = 1+z f \bigg(\frac{z}{1+z} \bigg)
$$
As an attempt, I tried a change of ...
0
votes
0answers
13 views
How to prove that a recursively defined contraction mapping on a sequence is convergent
I'm asked to prove the following statement:
Let $f$ be a contraction mapping on a complete metric space $M$ in the sense that
$$
d(f(x), f(y)) \leq c d(x, y), \quad \forall x, y \in M
$$
for some $c \...
0
votes
3answers
46 views
Solve the recurrence: $T(n) = \sqrt{2n}T(\sqrt{2n})+\sqrt{n}$
I found a recurrence of a similar form on this forum, but I couldn't use it to gain any intuition for my question. So far, I've tried 3 things. I've tried unrolling it but could not really see a ...
1
vote
1answer
32 views
How to solve this recurrence problem that may be related to register allocations
I am having trouble getting an analytical form for this recurrence (say call it problem R1):
$$
a_n = 2a_{n-1}\sqrt{1-a^2_{n-1}} \quad \text{for $n > 0$ with $a_0=1/2$}
$$
But a related ...
0
votes
0answers
13 views
Ackerman functions structural recursion
Suppose $ foldn : A \times (A \rightarrow A) \rightarrow \mathbb{N} \rightarrow A $ such that $foldn$ is structural recursion over naturals.
$foldn(c,h,m) = \left\{
\begin{array}{ll}
...
0
votes
0answers
24 views
What is the maximum (meaningful) number of iterations in the LSQR algorithm?
When applying the LSQR algorithm (-> https://web.stanford.edu/group/SOL/software/lsqr/lsqr-toms82a.pdf) to a $m \times n$ least squares problem $\mathbf{A}_{m \times n} \mathbf{x}_n = \mathbf{b}_m$ ($...
5
votes
3answers
164 views
How to construct a closed form formula for a recursive sequence?
In the Wikipedia page of the Fibonacci sequence, I found the following statement:
Like every sequence defined by a linear recurrence with linear
coefficients, the Fibonacci numbers have a closed ...
-1
votes
1answer
37 views
Solving the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$ [closed]
Solve the recurrence $T(n) = 3T(n/4) + n\log n , T(1) = 1$
Can someone help me to solve this recurrence using substitution method?
0
votes
1answer
12 views
Iterative Modeling of Decay to a Nonzero Constant
I would like to construct a recurrence function $f$ over some sequence $v_0,v_1,v_2,\ldots$ such that $f(v_t) = c$ for some nonzero constant $c$ as $t\to\infty$. Specifically, I would like $f$ to ...
1
vote
3answers
56 views
Consider the following sequence:
$a_j = 4a_{j-1} - 4a_{j-2}$
$a_0=0;\ a_1 = 1$
For all $j\geqslant2$, come up with a general formula for the term $a_j$.
Use mathematical induction to prove your claim.
I have calculated the ...
0
votes
1answer
46 views
How many repeated steps in a Fibonacci recursive function [closed]
how can i calculate how many repeated calls occur in a fib recursive function.
fib(n):
if n = 0 : ret 0
if n = 1 : ret 1
ret fib(n - 1) + fib(n - 2)
ex) if n = 5 how many times fib(...
0
votes
1answer
29 views
Exact number of steps in a recursion [closed]
I am studying algorithms and I came across this problem:
$t(1) = 1$ and $t(n) = 4t(n/2) + n^2$
Calculate the exact value of $t(n)$ for all $n=2^l, l \in N $
Initially I thought this would be a ...
0
votes
1answer
38 views
What is the difference between $O(n + \log n)$ and $O(n + n/2)$?
I've learned that when we see O(log n) we consider that a given problem is halve every time. So having O(n + log n) would be that we first iterate n times once and then the problem is continually ...
0
votes
1answer
31 views
Unable to verify recurrance $T(n) = T(n/2) + n$ via substitution
Currently studying "Introduction to Algorithms" , currently stuck at trying to verify an upper bound to a recurrence via substitution when I already know for sure from another method that it is ...
2
votes
1answer
26 views
Find the probability that the 2nd and 3rd order statistics are compared in the QuickSelect algorithm
A description of QuickSelect: In the selection problem, we have a list of numbers and want to find the ith order statistic. That's the ith smallest value, which is the value such that i-1 other ...
1
vote
0answers
22 views
Least Squares removing first $k$ observations Woodbury formula
Given the matrix $X_{n,p}$ from the least squares problem $$ \mathbf{X} \cdot \mathbf{\beta} = z $$
Where the normal equation is:
$$ \mathbf{\hat{\beta}} = \left(\mathbf{X}^T \mathbf{X}\right)^{-1} ...
1
vote
2answers
124 views
Algorithm runnning time $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + \sqrt{n} $ using substitution
I need to solve the following recurrence, only using the substituion method (CLRS):
$$ T(n) = \sqrt n \cdot T(\sqrt n) + \sqrt n $$
This is what I have done so far:
Changing variables
$$ m = \log_{...
1
vote
1answer
33 views
Estimating asymptotic runtime of recurrence-equation given recursive-tree
Given the following recurrence equation: $T(n) = T(n/2) + T(n/3) + n$
I need to use a recursive-tree to come up with an estimated $O$-notation for the runtime of this recursive algorithm, given above....
0
votes
1answer
43 views
How to show that a function is recursive?
I have a problem for the comprehension of how to prove that a function $ log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as:
$$log_2 (x)= \begin{cases}
y & \text{if $x=2^y$} \newline
\bot &...
-1
votes
1answer
26 views
Find the least absolute value of the sum of product of elements of two arrays, permutation being allowed
Given two arrays $\text{A}$ and $\text{B}$ with $\text{M, N}$ elements respectively, minimize :$$\left|\sum_{i=1}^{\text{M}} a_i b_{j_i}\right|$$ where $b_j \in B$.
This cannot be boiled down by a ...
