Questions tagged [recursive-algorithms]
Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
0
votes
1answer
32 views
Recurrence proof by induction
I'm having a hard time to understand how am i supposed to solve this question:
$T(n) = \sqrt{n}T(\sqrt{n})+n$. Prove by induction that $T(n) = \Theta (n \log{(\log{(n)})})$.
These are all the data ...
0
votes
0answers
14 views
How many balls will be left at the end of this process?
Consider having $N$ colored balls. Each color has at least $N/2k$ and at most $N/k$ balls in the beginning, for some parameter $k\ll N$.
At each iteration, we remove $k$ balls with different colors, ...
6
votes
1answer
73 views
Why does calculating $\exp z$ using $\ln z$ via newton-raphson method fail to converge?
I am trying to calculate $\exp z$ using $\ln z$ via Newton-Raphson method $$x_{n+1} = x_n-\frac{f(x_n)}{f^{'}(x_n)}$$and got the formula $$x_{n+1}=x_n-\frac{\ln x_n-z}{\frac{1}{x_n}}$$ where $z = a + ...
0
votes
1answer
27 views
Generating function from recurrence relation of binomial distribution
Hello i have given recurrence like this :
$$p_{n,k}=(1-q)p_{n-1,k-1}+qp_{n-1,k}$$
my question is how to get (step by step) generating function from this recurrence?
we know that it's some king of ...
0
votes
1answer
48 views
Quick Sort Question
Can anybody please help me out with this sorting question? I am new to the topic of sorting algorithm and just trying to complete the same.
Ques: Sort the below using Quick sorting algorithm
15, 10, ...
0
votes
1answer
18 views
$t(\lfloor\frac{n}{2}\rfloor)+t(\lceil\frac{n}{2}\rceil)+n=n(\lfloor\log n\rfloor+3)-2^{\lfloor\log n\rfloor +1}$
Given the following recurrence relation:
$t(1) = 1$
$t(n) = t(\lfloor \frac{n}{2} \rfloor) + t(\lceil \frac{n}{2} \rceil) + n$
How would a proof for the solution $t(n) = n (\lfloor \log n \rfloor +...
0
votes
0answers
13 views
Algorithm Complexity
Given an algorithm $\mathcal{A}$ with input parameter $\theta$ with the objective of obtaining $\theta^* = \lim_{k \rightarrow \infty} \mathcal{A}_k(\theta)$.
Say we are interested in characterizing ...
-2
votes
0answers
20 views
how to derive betweenness?
I have a question regarding the concept of betweenness in regards with order theory.There is an only example of betweenness available provided on the wikipedia page.
The example given is as follows.
...
2
votes
4answers
39 views
Convert Polynomial to Sum
I have to convert the polynomial: $P_4=x^4+7x^3-13x^2-103x-84$ into the form: $$P_4(x)=\sum_{i=0}^4 a_i(x-1)^i$$ using Horner's Method.
I can evaluate both of them using Horner's Method, but I can't ...
2
votes
1answer
50 views
Quick Sort worst case, why $n^2$?
I have a very hard time understanding this proof:
$$T(N) = T(N-1)+cN$$
$$T(N-1) = T(N-2)+c(N-1)$$
$$T(N-2) = T(N-3)+c(N-2)$$
$$\vdots$$
$$T(2) = T(1)+c(2)$$
$$T(N) = T(1)+c\sum_{i = 2}^{N} i = O\...
0
votes
0answers
91 views
Modified 12 coin puzzle
I was looking on to the classic 12 coin puzzle.
A slight modification to it:
If out of N coins, N-1 are genuine and 1 is fake(which may be heavier or lighter), is there a formula to calculate the ...
2
votes
1answer
39 views
Recursive algorithm probability
I'm trying to find the probability of obtaining a six on a dice roll following these rules:
You roll a dice and if you roll $6$, then you win.
However, if it is not $6$, you roll another dice....
1
vote
1answer
43 views
Can't figure out $O(n \log n)$ divide and conquer algorithm
For an $n$ that is a power of $2$, the $n × n$ Weirdo matrix $W_n$ is defined as follows. For
$n = 1, W_1 = [1]$. For $n > 1$, $W_n$ is defined inductively by
$W_n =
\left[
\begin{matrix}
W_\frac{...
0
votes
0answers
26 views
Conversion of this recursive formula to a general term of a sequence
I got puzzled trying to convert this particular recursive sequence to a general term of a sequence.
$$S_n=1+n+\sum_{j=2}^{n-1} j\times S_{n-j}\times\binom{n}{j}$$
Can somebody help me to reduce to ...
1
vote
0answers
50 views
Explicit to Recursive Formula
I've spent the day trying to figure out how to make this particular explicit formula recursive, and come up empty.
$v(t)=(0.98^t-1)\times3.92$
None of my searches helped me in converting this type ...
-1
votes
2answers
20 views
Proof of worst-case time complexity of Binary Search
I know that using the Master Theorem, one can easily arrive at the worst-case time complexity. However, how would I go about proving that it is in $O(lg(n))$ by defining upper and lower bounds? I have ...
0
votes
0answers
24 views
Recursive algorithm for planar graph
I have this pseudo-code and I need to understand what it does. It takes some planar graph as input and returns a subset of V (that are the vertexes of the graph). It is clearly recursive, but I don't ...
0
votes
1answer
64 views
Back-n-Forth or a Direct Isomorphism Between A Countable DLO Without Endpoints and $U = \{ \frac{m}{2^n} \}$
Note: I changed this question and deleted my answer, bringing it into the question for quick review. The proof now has the same brevity as the back-and-forth method found in wikipedia.
Let $P$ be a ...
1
vote
0answers
29 views
$f(n) = 2f(n/2) + n^2$ if n is even or $2f(n/2) + n^3$ if n is odd
I want to solve the following recursion to find the complexity.
$f(n)=\begin{cases}
2f(n/2) + n^2 & \textbf{if } n \text{ is even}\\
2f(\lfloor n/2\rfloor) + n^3 &...
0
votes
0answers
26 views
Number of levels in recursion tree.
See in the picture that the number of levels is clearly $1+\log_{4/3} n$.
so,the total cost should be $cn(1+\log_{4/3} n)$
However in clrs and Khan Academy article of Cormen they are doing $cn\log_{4/...
2
votes
2answers
48 views
Solution to differential equation $y'(x) = a * y(x)^2$
first of all: I am not a mathematician. I am struggling since a few hours with a simple differential equation which I would like to solve to approximate the expectation curve for computer simulations ...
1
vote
0answers
24 views
Trouble understanding a recursive summation
I'm reading an NLP paper. In section 4.2, there is the following summation:
$$\alpha[t][k] = \sum^{t-k}_{j=1}p(c^t_{t-k+1} | c^{t-k}_{t-k-j+1}) \cdot \alpha[t-k][j]$$
where $\alpha[0][0] = 1$.
...
2
votes
1answer
53 views
A little help for building the Fibonacci spiral in a particular reference system
In the following picture, the numbers represent the building steps of the Fibonacci spiral (or Golden spiral).
I would like to find the coordinates of the upper-left corner of the squares (black dots)...
1
vote
1answer
55 views
Does this recursive function have a closed-form solution?
Consider the following recursive function:
$$
z(i) = \begin{cases}
z(i + 8) + 1 & i < 0 \\
z(i - 7) & i > 2 \\
0 & 0 \leq i \leq 2
\end{cases}
$$
Does this recursive function have ...
1
vote
1answer
76 views
How can I write a recursive function having $\Theta(n^7)$?
How can I write a recursive function having $\Theta(n^7)$ cost?
I must only use if, then, else statements and a function called $G(n)$ that costs $\Theta(n)$.
For example:
...
0
votes
1answer
40 views
Principle of mathematical induction in recursive functions
"Use the principles of mathematical induction to show that the value at each positive integer of a function defined recursively is uniquely determined"
I have a problem understanding what exactly it ...
0
votes
1answer
203 views
Trying to simplify this
How do I simplify this into a formula?
Note: $z,g,o,x,p,b,c,f,y$ - are all multiplicative constants
I have:
$$n(1)=z\left(gox^0+p\left(\frac{b}c\right)-fy^0\right)$$
$$n(3)=z\left(gox^2+p\left(\...
0
votes
0answers
46 views
0
votes
1answer
55 views
Explicit form of recursive function
Given recursive function:
$$T(x)=2T(\frac{x}{2})+\frac{2}{\log (x)}$$
reach an explicit form:
We already solved it in class. However I can't seem to remember, how was it...
I Wrote it in these ...
0
votes
1answer
39 views
generating all possible k partition of an array
actually, I confronted a problem for generating all possible k partitions of an array. I tried to write the algorithm but actually, I am not able to.
can anybody please give me the idea, how to code ...
0
votes
1answer
39 views
finding a recursive formula for a sequence, if possible [closed]
Hi everyone: I was looking over an NYS Algebra 2 Regents, and two training programs for a long-distance race were compared. (The answer they wanted was the recursive formula for a simple arithmetic ...
0
votes
0answers
24 views
First Order Nonlinear Recurrence Relation
I am trying to solve the closed formula for $x_n$ given the first order non-linear recurrence relation below. Unlike linear recurrences with direct solutions, I can't find any good reference for non-...
2
votes
1answer
42 views
How can i distribute the money in the fewest movements? [closed]
I am trying to evenly distribute the total amount to each person involved.
For example I will use money.
Example 1
Person A has $20
Person B has $40
Person C has $60
So to make everything even ...
0
votes
0answers
25 views
Multiply large numbers by dividing them into 3 (Karatsuba with n/3 size)
I was solving some problems related to Karatsuba, when I came across a problem which says, how many multiplications would you need to multiply a large number divided into 3 smaller ones like this:
a =...
0
votes
3answers
76 views
How to write recursive formula as explicit (specifically, exponential)?
I recall learning in school how to convert arithmetic and geometric sequence formulas between recursive and explicit, but I don't remember learning a systematic method to approach it. For example, let ...
1
vote
2answers
43 views
find the largest square foot given an area
Given an area of n square foot, I need to be able to find the largest square foot I could make in the given area.
Example: if I had a total area of 12 square foot, I would be able to make one 3x3 ...
6
votes
1answer
229 views
Common roots of recursive defined polynomial
I have a series of polynomials $P_j(x)$ given by the recursive formula
$$P_{j+1}=\frac{e_j}{c_j}xP_{j}-\frac{f_j}{c_j}P_{j-1}
$$
with $P_{-1} \equiv 0$, $P_0 \equiv 1$, where
$$c_j = (j+1)(j+2\kappa+1)...
0
votes
1answer
49 views
Is there a rule behind why $\left \{ 1+(-1/2)^n) \right \}^{+\infty}_{n=1}$ is $a_{n+2}=1/2(a_{n+1}+a_{n}) , a_{0} = 2 , a_{1}=1/2$ in recursive form?
I understand that both expresions represent the same sequence of numbers. It starts at $a_{0}=2$ and oscilate around 1 converging to it from up and down.
I have been playing around with the explicit ...
1
vote
1answer
42 views
Visualize $T(n)=2T(n/2)+O(n)=O(n\log(n))$ on a Tree
I understand the mathematical proof for $T(n)=2T(n/2)+O(n)=O(n\log(n))$, however I cannot visually wrap my head around how it works. Intuitively, it just feels like it should $O(n^2)$. Can you show me ...
0
votes
1answer
42 views
Convergence of recursive scheme
I would like to see why below recursive scheme is convergent :
$x_{n+1}= \sqrt{\alpha\cdot x_n+\beta}$
Here, $\alpha>0$ and $\beta\in\mathbb{R}\setminus\left\{0\right\}$.
I tried something like:
...
2
votes
1answer
71 views
Dynamic Programming problem palindrome
I am stuck with the following problem:
Given a string of characters $w$, we want to know the minimum number of characters that we must add to $w$ in order to convert this string in a palindrome (note ...
0
votes
0answers
19 views
Hankel or Bessel functions of integer separated order evaluated at the same value
Let $H_\nu^{(1)}=J_\nu+iY_\nu$ be one of the Hankel function. If $\nu=\left|N-\alpha\right|$ with $N$ integer and $0<\alpha<1$, is there a fast way to get all $H_\nu^{(1)}(z)$ for all $\left|N\...
2
votes
1answer
60 views
What's the idea behind recursive least squares (RLS)?
The simply explanation of recursive Least squares (RLS) is:
$$\theta(t) = \theta(t-1) -P(t)\phi(t)[y(t) - \theta ^T(t)\theta(t-1)]$$
$$P^{-1}(t) = P^{-1} + \phi(t) \phi^T(t)$$
Where $\phi$ is the ...
0
votes
1answer
48 views
what is the complexity of recursive summation
Can someone tell me the exact complexity of this recursion ? this is actually formula for below question ( solved in recursive brute force way )
There is n steps stairs and a person standing at the ...
2
votes
1answer
76 views
*Numerical* Convergence of the Babylonian Method?
I understand the sequence $x_{n+1} = \frac12\left(x_n + \frac2 {x_n}\right) $ converges to $ \sqrt2 $ algebraically.
That is proved by means of fixed-point method or monotone convergence theorem and ...
0
votes
0answers
11 views
Simplification in Recursive Algorithms with tilde relationship
$f(N)\sim g(N)$ iff $|\frac{f(N)}{g(N)}|\rightarrow 1$ as $N\rightarrow \infty$.
Define $C_N$ to be the number of compares to sort $N$ elements and analyze $C_N$.
Given $\frac{C_N}{N+1} = (\frac{C_1}{...
1
vote
1answer
13 views
Basic Recurrence Problem in the Analysis of Algorithm
I am taking an algorithm course at Coursera. From this webpage by a Princeton Professor, Example 1.5 (Analysis of quicksort) gives the following codes.
public class Quick
{
private static ...
11
votes
3answers
738 views
How to tell if a particular number will survive in this sieve?
I was asked this in an interview.
We have people numbered from one to infinity: $$1, 2, 3, 4, 5, 6, 7, 8, \dotsc\,.$$ In first pass every 2nd person is killed, so we have $$1, 3, 5, 7, 9, 11,\...
0
votes
0answers
21 views
Graph algorithm to find the most likely ancestor of a node
I'm working on the Wikipedia Category Graph (WCG). In the WCG, each article is associated to multiple categories.
For example, the article "Lists_of_Israeli_footballers" is linked to multiple ...
1
vote
0answers
39 views
How to derive a recursive version of a regularised cost function
I am to derive a recursive version of the following cost function and examine for which choice of D can we have a estimator windup
$V(\theta) = \frac{1}{2}\sum_{t=1}^n(y(t)-\phi(t)^T\theta)^2 + \...
