Questions tagged [recursive-algorithms]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...

1
2 3 4 5
22