Stack Exchange Network

Stack Exchange network consists of 175 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
13 views

Fractional Knapsack Problem Linear Time

So I came across a solution to the fractional knapsack problem in linear time here: http://algo2.iti.kit.edu/sanders/courses/algdat03/sol12.pdf I'm not sure I understand the algorithm given. We ...
0
votes
1answer
22 views

Understanding the Master Theorem - Determining the levels of recursion

I am trying to understand the proof for the Master Theorem. I have started by unwinding the following recurrence in order to find the total running time of an algorithm whose time complexity can be ...
0
votes
0answers
7 views

Divided Differences expanded form definition.

From definition of divided differences we have that $$f[x_0,\cdots,x_n]=\sum_{j=0}^n\frac{f(x_j)}{\Pi_{{k\in\{0,\cdots,n\}-\{j\}}}(x_j-x_k)} $$ It makes completely sense to have $k\neq j$ otherwise ...
2
votes
1answer
32 views

Optimal permutation for differential storage

This is a practical problem I encountered recently. I'm convinced that it has been solved before, however I don't know where to start looking as I'm unfamiliar with all the terminology involved. Hope ...
1
vote
0answers
28 views

Why does chaotic behavior explode when $k > \pi$ for $f_{n + 1}(x) = \sin(kf_n(x))$?

Why does the recursion $f_{n + 1}(x) = \sin(kf_n(x))$ with initial conditions $f_0(x) = x$ quicly display global chaotic behavior when $k > \pi$? I have a very limited knowledge in nonlinear ...
2
votes
2answers
91 views

is there a faster method to calculate $1/x$ ($x$ an integer) than this?

I gave this stackexchange a second go. Is there a faster way to calculate $1/x$ than the following: Calculate $100/x$ (.or other arbitrary positive power of $10$) with remainder Write multiplier in ...
1
vote
1answer
21 views

Mathematical Induction for a defined Fibonacci Function

I'm a bit stuck on this problem and can't figure out how to proceed. We have the following Fib. recurrence given to us: $f(0;a,b) = a;$ $f(1;a,b) = b;$ $f(n;a,b)=f(n-1;b, a+b)$ The problem defines ...
2
votes
0answers
41 views

How to determine how fast something is going towards infinity?

Just for a little bit of information I'm more of a programmer and less a mathematician so if some of my terms seem out of place it is due to a lack for formal training in Math. While working on my ...
0
votes
0answers
32 views

Longest Increasing Subsequence Using Divide-And-Conquer

I'm required to solve the LIS problem using Divide-and-Conquer. The hint provided is the following: For each position in the array find the cardinality of the longest sequence that ends up with it, ...
0
votes
2answers
29 views

Sinusoidal Generation in Recursive Algorithm

I need to generate sinusoidal values for varying frequencies. I'm making a DTMF tone generator but I must generate my own values of sine using recursive algorithms. The exact wording of how I'm ...
0
votes
3answers
61 views

Solving a recurrence relation: can't figure out how to convert from summation

I am really struggling to solve this recurrence. $$ T(n) = T(\sqrt{n}) + n. $$ I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, ...
1
vote
1answer
28 views

$(G,\cdot)$ and $M \subseteq G$. Prove that the following algorithm computes the subgroup generated by M.

Let $(G,\cdot)$ be a finite group and $M \subseteq G$, $M\ne \emptyset$. Prove that the following algorithm computes the subgroup generated by M : $$S_{0}:=\{{e}\} , H_{0}:=\{{e}\}\\ S_{n+1}:=(S_{n}\...
0
votes
0answers
11 views

How can I compute recursive QR-factorization?

I wonder if it's possible to find the $Q$ and $R$ matrices from this QR-equation with only compute QR at one time only: $$A = QR$$ if, the first column of $A$ got removed and then a new column got ...
1
vote
1answer
176 views

Variance of parameter estimate using recursive least squares

I am learning about recursive least squares estimation using a forgetting factor $\lambda$ as a tool for treating time variations of model parameters and have become stuck on the following problem. ...
-1
votes
1answer
26 views

show algorithm to compute square root converge. [closed]

Consider the calculating the square root as follow: Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=\frac{g+\...
-1
votes
2answers
117 views

Solve the operations needed for the recursive formula

$f(n) = 1+\frac{1}{n}\sum_{i = 0}^{n - 1} f(i)$ Base case: $f(0) = 0$ how can I solve the recurrence?
0
votes
3answers
37 views

sequence that adds its previous results

Let $x = 0.3$. The first number of the sequence is $x$. The second number is the first number + $(0.3\cdot 0.3)$. The third number is the second number + $(0.3\cdot 0.3\cdot 0.3)$. This is a ...
0
votes
0answers
21 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
0
votes
2answers
30 views

What is a goal of Galileo's magnetometer recursive filter

I'm designing the basics of space magnetometer instrument for academic project and I came across a Galileo mission investigation document, with data flow described in chapter 6. As a first ...
1
vote
2answers
42 views

proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values

my question is involving the Ackermannfunction. Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following ...
0
votes
1answer
31 views

How to prove that class of “recursive” and “recursively enumerable” languages are not equal?

I would like to formulate a formal proof for showing that the classes of recursive and recursively enumerable languages are not equal. I know that recursive languages are accepted by Turing machines ...
0
votes
1answer
35 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
16 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
82 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
44 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
55 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
21 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
14 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
4answers
42 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 ...
1
vote
1answer
56 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
107 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
46 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
55 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
29 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
25 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
69 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
34 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
53 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
50 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
27 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
56 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
56 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
43 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
204 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
68 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 ...