Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1,354
questions
2
votes
1
answer
159
views
Reasoning about the Collatz conjecture, multiple infinitely growing trees that never overlap? [closed]
I have been pondering the Collatz conjecture recently as a mental exercise, and have run into a problem that has to do with proving that an iteratively growing tree of odd positive integers will ...
- 55
-2
votes
1
answer
48
views
Generate set of numbers containing 3 consecutive 1, but without the elements of the previous set [closed]
So I have this specific problem that I couldn't figure out. I want to create a set $F_n$ containing all bitstrings that has 3 consecutive 1s, but not those that are already contained in all the ...
- 713
0
votes
1
answer
57
views
Division based recurrences instead of subtraction based: $F(x)=F(x/2)+F(x/3)$
The most famous (and simplest non-trivial) recurrence is the Fibonacci recurrence $F(n)=F(n-1)+F(n-2)$ with $F(0)=0, F(1)=1$. What if we consider instead division based recurrences, the simplest non-...
- 8,945
0
votes
0
answers
27
views
How to best approach a numerical computational solution towards matching $e^{-r}$ and $k_2\sin(k_1\,r)$ as well as their derivatives $\frac{d}{d\,r}$?
In my question, "Why does it seem like two parameters $k_1$ and $k_2$ are needed to match $e^{-r}$ and $k_2\sin(k_1\,r)$ as well as their derivatives $\frac{d}{d\,r}$?", it was identified ...
- 951
0
votes
1
answer
105
views
Why doesn't this diagonal argument work?
I have a question about the standard rules for computing p.r. terms (see below). It seems pretty clear that these rules could be used to define a p.r. operation that evaluates any p.r. term of the ...
- 27
0
votes
1
answer
39
views
How to Prove Division of One Bezier Curve into Two using de Casteljau Algorithm
$\newcommand{\brstbasis}[2]{b^{#1}_{#2}}$
$\newcommand{\posintset}{\mathbb{Z}^{+}}$
$\newcommand{\intset}{\mathbb{Z}}$
$\newcommand{\realset}{\mathbb{R}}$
$\newcommand{\domain}[1]{\operatorname{dom}\...
- 1,840
0
votes
0
answers
23
views
Recursive approximations of inverse square law
I have a toy electrostatics simulation that consists of some number of 2D point particles that each have a real-valued "charge" $q_i$, which then exert forces on each other proportional to $...
- 640
0
votes
1
answer
120
views
Tried finding an efficient algorithm for a 4-digit number guessing game, knowing only the number of digits on correct positions..
I've been playing a game similar to Bulls and Cows, but it goes like this: one player has to pick a random $4$ digit number. Digits can repeat, any digit between $0$ to $9$ and, you only get the ...
- 3
0
votes
2
answers
21
views
Find limit of Decrementing Recursive Series
I want to find a formula to find the lower limit part of this recursive or geometric series
$$
x_{n} = \left( x_{n-1} + p \right) \times \left( 1 - \frac{t}{100} \right)
$$
I was just wondering what ...
- 13
0
votes
4
answers
107
views
Prove that $x_{n+1} = \frac{1}{3}(2x_n + \frac{a}{x_n^2})$ is decreasing
Prove that $x_{n+1} = \frac{1}{3}(2x_n + \frac{a}{x_n^2})$ is decreasing where $x_1$ $> 0$.
I have been asked the above question and the working out given to me skipped some steps in between.
It ...
- 618
0
votes
1
answer
36
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
1
vote
1
answer
29
views
Lemma 6.2. in Scaling Algorithms for the Shortest Path Problem
I have a question regarding the proof of Lemma 6.2. in this paper: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/scaling%20algorithm%20for%20the%20shortest.pdf.
The simplified ...
- 102
2
votes
1
answer
77
views
Let $x_0 = 3;\ x_{n+1}=3x_n\ $ if $\ \frac{x_n}{2}<1;\ x_{n+1}=\frac{x_n}{2}\ $ if $\ \frac{x_n}{2}>1.\ $ Is $\ \liminf_{n\to\infty} x_n=1?$
This is a natural follow-up question of this previous question of mine.
Let $x_0 = 3.$ Let $\ x_{n+1} = 3x_n\ $ if $\ \frac{x_n}{2}<1;\quad x_{n+1} = \frac{x_n}{2}\ $ if $\ \frac{x_n}{2}>1.\quad ...
- 20.7k
0
votes
0
answers
25
views
Further explain natural language explanation for statements deduced from master theorem for solving recurrences
This content is taken from from Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 2022, Chapter 4.
Given the following recurrence ...
- 81
3
votes
2
answers
190
views
Guaranteed graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 53
0
votes
0
answers
27
views
Finding an algorithm that goes through all the possible permutations of a set only by swapping 2 elements
I recently came across a problem when trying to deal with a set of numbers with n elements.
The problem is as follows:
Starting with a set of n distinct elements, how would one generalize a unique ...
0
votes
0
answers
36
views
Subset Product has a pseudo-polynomial algorithm?
Subset Product- Given $N$ and a list of positive divisors $S$, decide if there is a product combination equal to $N$
We will sort $S$ in numerical order from smallest to largest in order
to find out ...
- 191
7
votes
1
answer
213
views
Prove or reject my solution to "How quickly can you type this unary string?"
I had posted an answer on the Code Golf SE yesterday. Although the answer on that site remain valid if no counterexample can be find. I'm interesting in its correctness. So I want to find a prove or ...
- 182
6
votes
2
answers
222
views
What is the set generate by ${1}$ and a function $1/(a+b)$?
If I'm given a starting set, and an operation, what would the generated set looks like?
Here we take $S_0=\{1\}$ and $f(a,b) = \dfrac{1}{a+b}$ as an example, the following Mathematica codes shows the ...
- 465
1
vote
1
answer
24
views
Does my proof that the recurrence $T(n) = T(\frac{n}{2}) + d = \Theta(lgn)$work?
Suppose we have the recurrence
$T(n) = T(\frac{n}{2}) + d$ if $n = 2^j$ and where is some integer greater than $0$ (i.e n is even). I know that this recurrence is $\Theta(lg(n))$, and I want to prove ...
- 496
-1
votes
1
answer
62
views
Division algorithm proof intuitive [closed]
The following algorithm can be used for division. Can someone intuitively explain or offer proof that quotient returned from recursive call (say q') is such that ...
- 81
0
votes
0
answers
28
views
Understanding base cases of inductive proofs in algorithm analysis Cormen et al
I am currently working through Cormen et al's classic book on algorithms and data structures. I am trying to follow an inductive substitution proof that the following time complexity function is $O(n\...
- 496
0
votes
1
answer
52
views
Telescoping recursive term ${D(h) = D(h-2)+1}$
In the context of Computer Science, I am trying to calculate the maximum depth difference between leaf nodes in any existing AVL-Trees of height $h$. I don't think any knowledge of AVL trees is needed,...
- 342
0
votes
1
answer
28
views
Fast algorithms for computing $AGA^T$ with $G$ PSD symmetric.
Problem:
In the context of decision making in some optimization problems, I found that it is meaningful to compute $AGA^T$ with $A\in\mathbb R^{m\times n}$ and $G\in\mathbb R^{n\times n}$ a PSD ...
- 6,076
2
votes
2
answers
94
views
3d fractal helix modeling
I'm trying to build a 3d visual to illustrate a concept. Imagine a circular helix. We could define a cylinder that contains that helix. But now imagine this cylinder takes the helicoïd shape too ! We ...
- 23
1
vote
0
answers
128
views
How do I convert my recursive algorithm to an explicit formula? [closed]
I have the recursive formula:
\begin{align}
x_1&=1-\frac{1}{e} \\
x_{n+1}&=1-(1-x_n)^{1/x_n}
\end{align}
Is there any way to write this as an explicit formula? I've tried writing the exact ...
- 11
-1
votes
1
answer
61
views
Divide and conquer algorithm problem applied to an n x n-matrix of n players competing in a chess tournament [closed]
A total of n players have competed in a chess tournament. In particular every pair of players i and j played one single game. All results of the tournament are encoded in a n × n-matrix A, where for ...
- 27
1
vote
1
answer
52
views
What is the pattern and the solution to this system of equations?
I would like to find the general solution to the following system of equations:
$$ x_1 + k_1 + \sum_{i=1}^N A_{1,i}x_i=0 $$
$$ x_2 + k_2 + \sum_{i=1}^N A_{2,i}x_i=0 $$
$$\vdots$$
$$ x_N + k_N + \sum_{...
0
votes
1
answer
104
views
Expressing a Recursive Sequence in a Non-Recursive Form
I am working on a recursive sequence and wondering if it's possible to convert it into a non-recursive form. The sequence is defined as follows:
$$ a_n = a_{n-1} \times (n + 1) + n! $$
with the ...
- 81
0
votes
0
answers
26
views
Recursive function with a one integer parameter
I am trying to come up with a recursive function which takes a single integer as a starting value. Just a single example is provided and initial value is 9. Example is as follows:
Input:
9
Output:
...
- 1
0
votes
0
answers
50
views
What is the general form of this recurrence formula? [duplicate]
Here is a way to solve it but how should I find the general form and verify it ?
The last step is the where we will conclude the general form from it and then verify it:
T(n) = nT(n-1) + 1 , T(0) = ...
- 11
-2
votes
2
answers
102
views
i need help with this recursive problem: $T(n) = nT(n-1) + 1$, $T(0) = 0$. [closed]
Now here I solved everything but I’m now stuck at the general form how am I gonna write the general form with the (pi) product summation ?
Hint there’s something related also with combination and ...
- 11
0
votes
0
answers
61
views
Mathematical Induction to Prove Binary Search for First Occurrence of an Element in a Sorted Array
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}$
$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}$
$\...
- 1,840
3
votes
1
answer
73
views
Solving the recurrence equation : $T(n) = 2T(n/2) + n^2$
Where $T(1)=1$ and assuming that $n=2^k$ and that $k\ge 0$ and that the Master Theorm can't be used.
What I tried:
$T(n) = 2T(n/2)+n^2$
Following backwards substitution to get a pattern:
$T(2^k)=2T(2^{...
- 31
14
votes
3
answers
3k
views
What is the sum of an infinite resistor ladder with geometric progression?
I am trying to solve for the equivalent resistance $R_{\infty}$ of an infinite resistor ladder network with geometric progression as in the image below, with the size of the resistors in each section ...
- 1,111
0
votes
0
answers
84
views
How to solve this recurrence $T(n) = 2T(n/2) +O(n\log n)$
Problem: Inspiring by the following post, I wonder how to solve the recurrence
$$ T(n) = 2T(n/2) +\mathcal{O}(n\log n).$$
I had just thought about this question already when I saw the above post. I ...
- 1,238
0
votes
1
answer
65
views
Find the number of sequences related to XOR
Given a positive integer $n$, I want to find the number of sequences starting with $1$ and ending with $n$, such that every two adjacent elements $i,j$ satisfy $j\oplus i<j$ and $j>i$ ($\oplus$ ...
- 23
0
votes
0
answers
16
views
Calculate pre-factors for recursive function for arbitrary steps
I have a simple recursive function:
$f(i+1)=\frac{1}{2}f(i)+\frac{1}{2}a$
both f(i) and a are numbers between 0 and 1, while a can change its value while iterating over the function f.
So lets say, ...
- 31
2
votes
1
answer
102
views
Find a recurrence relation for the number of bit strings of length n that contain consecutive symbols that are the same
Here is my attempt:
First there is $2 \cdot 2^{n-1}$ ways if string ends with $00$ or $11$.
Second there are ways when string end with $10$ or $01$. So it will give us $a(n-1)$ ways to solve ...
- 25
2
votes
1
answer
151
views
What algorithm has the best runtime?
Suppose you are choosing between the following three algorithms:
Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then ...
- 21
1
vote
1
answer
88
views
How do I write the induction hypothesis when dealing with recursive formulas
The sequence $ \{a_n\}_{n=0}^{\infty} $ is recursively defined by $ a_0 = 0 $, $a_1 = 1 $, $a_2 = 4 $ and
$a_n = a_{n-1} + a_{n-3} - n^2 + 8n - 10$
for $ n \geq 3 $.
Prove using induction or strong ...
- 35
0
votes
0
answers
44
views
How to solve a recursion to find a closed form solution?
I have the following recursive process:
$f_n(t) = e^{t-1} f_{n-1}(1-(1-p)(1-t))$
The initial condition is that $f_0(t) = 1$
I calculated that $f_1(t) = e^{t-1}$
And then I also calculated $f_2(t), f_3(...
- 235
0
votes
1
answer
56
views
What is this kind of recursion?
Consider the following expression:
For any fixed integer $a$, for real $x_i$
Pick an $x_0$ such that
$ln(ln(a))/ln(ln(a*100*x_0))=x_1$
Then substitute $x_0\mapsto x_1$
$ln(ln(a))/ln(ln(a*100*x_1))=x_2$...
- 591
1
vote
0
answers
110
views
2SUM variant with 2 arrays
I've been racking my brain trying to figure this out. I think I came up with a solution but its not elegant at all, I was wondering if any of yall could think of anything else. This is the problem
<...
0
votes
0
answers
36
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
0
votes
1
answer
62
views
Proving this partial computable function cannot be total computable
I am studying a qualifying exam and this computability theory question has been bothering me for days, so I am hoping to get help.
An infinite set $X\subset\omega$ is called immune if it contains no ...
- 782
0
votes
1
answer
93
views
Complexity of recursion with floor division $f(N) = F(N) - \sum_{m=2}^N f \left(\left\lfloor\frac N m \right\rfloor\right)$
Often in computational number theory, to compute $f(N)$, there are identities like
$$F(N) = \sum_{m=1}^N f \left(\left\lfloor\frac N m \right\rfloor\right) $$
where $F(N)$ is easy to compute, i.e. $O(...
- 10.9k
1
vote
1
answer
99
views
Big-O analysis of recurrence relation
I'm not sure if I should be posting this question here or under Stackoverflow, but given that it's algorithmic analysis, I figured Math was the right call. I have 2
functions that I'm trying to find ...
- 29
2
votes
1
answer
62
views
domain of a recursive function
Let's consider the recursive function defined as follows:
$$T(n)=T(\frac{n}{2})+1$$
However, it's important to clarify the domain of this function, specifically, the values of '$n$' for which it is ...
- 375
0
votes
1
answer
120
views
Big-O complexity of a recurrence function $8 \cdot T(\frac{n}{4})+O(n\cdot\sqrt{n})$
An algorithm solves a problem of size $n$ by recursively calling
8 subproblems, with each subproblem of 1/4 the size of the original input.
It then combines their solutions to form the solution of the ...
- 11