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
0answers
20 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
46 views

Divide and conquer: Why $F(0) = 0$? [on hold]

Reading algorithms. Fibonacci example. I saw an example where it said $F(1) = 1$ and $F(0) = 0$. (Fibonacci) Why $F(1) = 1$ and $F(0) = 0$? From where does it originate? Thanks.
0
votes
1answer
61 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
votes
0answers
23 views

Multiple equations dependent on each other

I am trying to process the trade data of 1,000+ cryptocurrencies across 25+ different crypto exchanges. I cannot figure out how to calculate the average price for each coin. First, the formula to ...
1
vote
0answers
26 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
24 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
47 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
23 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
42 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)...
0
votes
0answers
12 views

Prove that the time it takes to run the merge sort algorithm on a list of n numbers is less than an equation

Problem Can someone help me with this. I use strong deduction and then I have $T_{k} = 2^kT_{\dfrac{n}{2^k}}+kn$ but I don't know what to do next.
1
vote
1answer
50 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
71 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
198 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
53 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
25 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
21 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
39 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
23 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
49 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
41 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
227 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
40 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
59 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
18 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
48 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
44 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
66 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
727 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
18 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 + \...
0
votes
2answers
27 views

An algorithm to make a variable the sole term of one side

Is it always possible to refactor an equation so that a desired variable appears as the sole term of one side?* If so, how? Simple example: $$xa = ya + b \\ xa - ya = b \\ a(x - y) = b \\ a = \frac{...
2
votes
2answers
40 views

Finding a recurrence for $t_n$ that holds true for a set of integers

I know the answer but I have no idea how to explain it Question A $t_3 =$ ['aaa', 'abb', 'acc', 'bba', 'cca'] ($5$ elements) $t_4 =$ ['aaaa', 'aabb', 'aacc', 'abba', 'acca', 'bbaa', '...
0
votes
2answers
51 views

Confusing symbols

I saw these symbols in the text book for a subject i'm taking next semester, and I am just curious about what they mean. What is the question asking me?
0
votes
0answers
49 views

Stuck Simplifying for a Fibonacci Series

I am attempting to solve for $n$ in the equation: $g_n=g_1F_{n-1}+g_2F_n$ where $F_n$ is the $n$th Fibonacci number. I know that $g_0$ and $g_1$ will be positive integers such that $0 < g_1 \...
1
vote
0answers
74 views

What is the difference between Kalman Filter and Recursive Least Squares? [closed]

I wish to understand the difference between Kalman Filter and Recursive Least Squares since both of them use prediction and correction approach. In Kalman filter, the value of existing state vector ...
0
votes
0answers
9 views

Particle Filters: whether current measurement depends on previous measurement

Recently I was learning basic estimation theory. I am confused that whether the measurement $z_k$ is related to previous measurements $z_{1:k-1}$. A quick recap of the estimation problem. Given ...
0
votes
0answers
15 views

Solving Recurrence to Find Asymptotic Behavior (Algorithm)

Can somebody check if I got the right answers for those recurring functions? 1)$T(n)=4T(\frac{n}{3})+nlg^2n$ - using the asters theore i got that $T(n) \: \in \: \Theta(n^{\log_{3} 4}) \approx \Theta(...
1
vote
0answers
98 views

Longest path of a matrix

Given a matrix $$ A = \begin{pmatrix} 1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7 \end{pmatrix} $$ We know that the length of the longest path that is ...
0
votes
1answer
41 views

Prove $N\cdot lg(N) = \sum_{k=1}^N(\lfloor lg(k) \rfloor + 2)$ - “Analysis of Algorithms” by R. Sedgewick

This is a problem from "Analysis of Algorithms" by R. Sedgewick. In the context of the merge sort: $C_N = N\cdot lg(N)$ Exercise 1.4 Develop a recurrence describing the quantity $C_{N+1} − C_N$ ...
0
votes
6answers
154 views

Finding a recursive formula/sum for $\pi$

I'm very much aware of the $$\pi = 4 \left(1 - \frac13 + \frac15 - \frac17 + \frac19 -\cdots \right)$$ and $$\pi = \sqrt{6\left(1 + \frac14 + \frac19 + \frac{1}{16}+ \cdots \right)}$$ and even less ...
0
votes
0answers
21 views

Find an alternative FPTAS for knapsack

There is a famous algorithm using, the recusive integer data problem on: w(j,p) = min weight set of items of profit=p when we have j items Now I was wondering if there was an alternative solution ...
0
votes
0answers
45 views

Expand recursive equation to convert it into a normal formula

The Problem: I am faced with the following recursive equation: $$V(n) =\begin{cases} 2V(n/2)+n& \text{for n > 1}\\ 0 &\text{for n = 1} \end{cases}$$ I am trying to expand the function ...
0
votes
1answer
274 views

recurrance with merge-sort

Trying to modify a merge sort by recursively splitting an array of size n into k sorted subarrays k > 2 and merging these subarrays. Time for merging is c(k-1)n. Specify the recurrence relation and ...