Skip to main content

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
3 votes
1 answer
133 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 ...
Jookos's user avatar
  • 57
-2 votes
1 answer
47 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 ...
Kim Dong's user avatar
  • 713
0 votes
1 answer
56 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-...
D.R.'s user avatar
  • 8,885
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 ...
Stephen Elliott's user avatar
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 ...
nontology's user avatar
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}\...
Ziqi Fan's user avatar
  • 1,840
0 votes
0 answers
22 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 $...
redroid's user avatar
  • 640
0 votes
1 answer
101 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 ...
nex's user avatar
  • 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 ...
MrShoe's user avatar
  • 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 ...
Oofy2000's user avatar
  • 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 ...
sor3n's user avatar
  • 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 ...
Botanicus's user avatar
  • 102
2 votes
1 answer
71 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 ...
Adam Rubinson's user avatar
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 ...
jam's user avatar
  • 81
3 votes
2 answers
185 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 ...
user555076's user avatar
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 ...
You Know Who's user avatar
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 ...
The T's user avatar
  • 191
7 votes
1 answer
212 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 ...
tsh's user avatar
  • 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 ...
Nekomiya Kasane's user avatar
1 vote
1 answer
23 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 ...
Dan Öz's user avatar
  • 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 ...
jam's user avatar
  • 81
0 votes
0 answers
27 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\...
Dan Öz's user avatar
  • 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,...
Michel H's user avatar
  • 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 ...
P. Quinton's user avatar
  • 6,076
2 votes
2 answers
92 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 ...
nnuuurrrrcc's user avatar
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 ...
Joseph McCoy's user avatar
-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 ...
Marc Delos's user avatar
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_{...
FriendlyNeighborhoodEngineer's user avatar
0 votes
1 answer
103 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 ...
Diogo Sousa's user avatar
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: ...
Quiccc's user avatar
  • 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) = ...
Leo's user avatar
  • 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 ...
Leo's user avatar
  • 11
0 votes
0 answers
60 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}$ $\...
Ziqi Fan's user avatar
  • 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^{...
MM7654DDD's user avatar
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 ...
KDP's user avatar
  • 1,111
0 votes
0 answers
83 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 ...
Tung Nguyen's user avatar
  • 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$ ...
Abraham's user avatar
  • 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, ...
Marc Laub's user avatar
2 votes
1 answer
99 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 ...
High Tekk's user avatar
2 votes
1 answer
150 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 ...
Marff's user avatar
  • 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 ...
yunolol's user avatar
  • 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(...
Shatarupa18's user avatar
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$...
Pythagorus's user avatar
1 vote
0 answers
109 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 <...
Steve Harrington2's user avatar
0 votes
0 answers
35 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 ...
hunterlineage's user avatar
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 ...
mathlearner98's user avatar
0 votes
1 answer
92 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(...
qwr's user avatar
  • 10.9k
1 vote
1 answer
97 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 ...
Kevin's user avatar
  • 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 ...
Ariana's user avatar
  • 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 ...
user1230265's user avatar

1
2 3 4 5
28