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
5 votes
2 answers
90 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 ...
猫宮かさね's user avatar
1 vote
1 answer
18 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
0 votes
0 answers
59 views

Convergence to 9 in Iterative Functions Inspired by the Collatz Conjecture [closed]

Inspired by the Collatz Conjecture, I have explored a variant that introduces an additional element x, altering the operation for odd numbers and exploring convergence towards the numbers 36-18-9. ...
José Luis's user avatar
0 votes
1 answer
48 views

Division algorithm proof intuitive

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 ...
sam's user avatar
  • 1
0 votes
0 answers
25 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
49 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
  • 252
0 votes
1 answer
24 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
  • 5,979
2 votes
2 answers
75 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
121 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
54 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
47 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_{...
Nikola Ristic's user avatar
0 votes
1 answer
91 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
23 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
49 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
100 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
51 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,816
3 votes
1 answer
69 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
2k 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,079
0 votes
0 answers
72 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,248
0 votes
1 answer
62 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
15 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
60 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
118 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
84 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
53 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
93 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
30 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
57 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
71 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.7k
1 vote
1 answer
89 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
55 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
  • 369
0 votes
1 answer
111 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
0 votes
1 answer
205 views

Finding the Recurrence Relation of a Method

The answer key states this algorithm is O(log n). I was expecting the recurrence relationship to be T(n) = 2T(n/2) + 2, therefore, the answer key renders my hypothesis as false. Question: How is this ...
anon60707's user avatar
0 votes
0 answers
47 views

How to define multivariable double recursive function

I have a question for those who are familiar with recursion theory. According to Wikipedia (https://en.wikipedia.org/wiki/Double_recursion), Raphael M. Robinson called functions of two natural number ...
glutaminemusic's user avatar
0 votes
0 answers
96 views

Algorithm for non-linear system of equations

I would like some tips in figuring out a good algorithm to find the solution of the following system. Let $\theta$ be a constant in $(0,1)$, let $i,l=1,...,N$, let $a_{l}$ and $b_{i,l}$ be some ...
Andres's user avatar
  • 75
-4 votes
1 answer
122 views

Solving the recurrence $T(1) = 1$, $T(n) = T(n-1) + n^2$ [duplicate]

How do you solve the following recurrence? $T(1) = 1$ $T(n) = T(n-1) + n^2$
SlayersOfAll's user avatar
0 votes
1 answer
44 views

Asymptotic Bound [closed]

$$T(n) = \Theta \left ( n^{1/2} \left ( 1 + \int_1^n \frac{1}{u^{3/2}}\ du \right ) \right ) = \Theta \left ( n^{1/2} \right )$$ This asymptotic bound is evaluated to be $n^{1/2}$ but isn't the ...
Azhar's user avatar
  • 23
0 votes
1 answer
360 views

Solve the recurrence $T(n) = 2T(n-1) + 1$

The recurrence $T(n) = 2T(n-1) + 1$ has the solution $T(n) = O(2^n)$. show that a substitution proof fails with the assumption $T(n) <= c2^n$, where $c>0$. Then show how to subtract a lower-...
Matt Joy's user avatar
0 votes
1 answer
61 views

How was the solution to this recurrence obtained?

I am trying to understand the solution to the following recurrence. $I(n) = 1+n/B$ if $n \leq \alpha M$ and $I(n) = 4I(n/2)+1$ otherwise. The solution, according to the paper this is from, is $I(n) = ...
user308485's user avatar
  • 1,229
0 votes
0 answers
58 views

Induction Proof of Loop Invariance Given the Invariance

Consider the following program segment i=1 total = 1 while i<n i = i + 1 total = total + i Let p be the proposition "total = $\frac{{i}{(i+1)}}{2}$ &...
Rikiita's user avatar
0 votes
1 answer
63 views

Recurrence and Big-O - Question 1) T(n)=T(√n)+Θ(log(log(n)) and T(2)=0.

I'm trying to solve the recurrence. Runtimes and recurrence solutions. For initial conditions T(2) = 0, solve for; T(n)=T(√n)+Θ(log(log(n)) (recursive relation). ...
Aygen Ergen's user avatar
3 votes
1 answer
79 views

Find Pattern of a Recursive Definition

Premise I have been playing around for fun with the following recursive relation: $$ f(1) = \frac{a_1}{2} $$ $$ f(n+1) = \frac{a_{n+1} - \sum^n_{k=1} f(k) * f(n-k+1)}{2} $$ Where $a_n$ is a sequence ...
tkellehe's user avatar
  • 177
0 votes
1 answer
343 views

Using greedy algorithm to get the minimum total cost of adding a whole array

I meet a question about calculating adding all the elements of an array, each time we can only add two numbers, and the cost is the sum of these two numbers. so my solution (maybe not correct) is to ...
Helen Guo's user avatar
0 votes
1 answer
114 views

Knapsack problem with overload

Let $N = \{1, 2, \ldots, n\}$ denote a set of items, $w \in \mathbb{R}_{++}^N$ a vector of weights, $c > 0$ a constant and $x \in \{0, 1\}^N$ a decision variable. The objective is to minimally ...
clueless's user avatar
  • 771
0 votes
1 answer
96 views

Recurrence for inverting a matrix

I am reading the Chapter 28 Matrix Operations Section 2 of Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. I particularly need help with understanding Theorem 28.2 (Inversion is no ...
boil's user avatar
  • 125
0 votes
0 answers
116 views

How to solve a recursive convolution equation

In the most general case, I ask how to solve (either analytically or numerically) this equation for $x(t)$ $$x(t) = \int_{-\infty}^t g(t-\tau) f\big(x(\tau)\big) d\tau$$ where $f, g$ are functions ...
Neo's user avatar
  • 251
2 votes
0 answers
54 views

Understanding the characteristic equation for solving linear homogeneous recurrences

We have a recurrence of the form $a_0t_n + a_1t_{n-1} + ... + a_kt_{n-k}= 0$, with $k$ initial conditions, i.e. for $a\leq i < a+k$, $t(i) = b_i$, where $b_i$ are constants. There are infinite ...
Heng Wei's user avatar
  • 419
0 votes
0 answers
81 views

Number of initial conditions required for a pair of multivariable recursion relations

I have the following pair of recursion relations for $f_{m,n}$, featuring two indices/variables $(m,n)$: $$\sin{\left(\frac{n \hbar}{2} \right)} f_{m+1,n} - \sin{\left(\frac{m \hbar}{2} \right)} f_{m,...
user8675309's user avatar
0 votes
1 answer
61 views

Solve the recurrence equation - troubleshooting

Solve the recurrence equation: $T(n) = 2T(n/3) + 3 n^2$. Assume $T(0) = T(1) = O(1)$. Use the substitution and pattern recognition method. My idea: $$T(n/3) = 2T(n/9) + n^2$$ Insert: $$T(n) = 2 (2T(n/...
xx33xx44's user avatar

1
2 3 4 5
27