Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 + \...