All Questions
Tagged with recursive-algorithms recursion
268
questions
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
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
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
-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
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
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
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
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
0
votes
0
answers
63
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 ...
-4
votes
1
answer
129
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$
0
votes
1
answer
45
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 ...
- 23
0
votes
0
answers
161
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 ...
- 251