Questions tagged [recursive-algorithms]

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

Filter by
Sorted by
Tagged with
1 vote
0 answers
15 views

Non-recursive algorithm with exponential running time

It is well-known, that there are many recursive algorithms running in exponential time, e.g. branching algorithm, backtracking etc. . My question is, is it possible to construct a non-recursive ...
user avatar
0 votes
0 answers
30 views

Getting rid of asymptotic notation in Recurrence Relations

Let's suppose I want to resolve the following Recurrence Relation: $$ T(n) = \begin{cases} 1 & n=1 \\ T(n-1) + \Theta(n) & \text{otherwise} \end{cases} $$ I want to prove that ...
user avatar
0 votes
1 answer
25 views

Is it possible to obtain rotation or transposition with following rules?

I have been trying to solve a problem in which I faced this question which I need to answer to solve my problem. Any help or suggestions or references would be helpful ? Given a sequence of length ...
user avatar
  • 62
0 votes
2 answers
69 views

Quite challenge: how to solve this functional equation?

I have asked This question before, but I forget to add some term and factors. When adding those, the difficulties increased significantly. Consider the following equation: $$\omega(t) = 1 + \frac{2}{t^...
user avatar
2 votes
0 answers
58 views

What is the general techique to solve the following type of recursive integrals?

Consider the recursive definition of the following function: \begin{equation} \omega(t, a) = 1 + \frac{1}{t} \cdot \biggl( \int_{0}^{t-a}\! \omega(t-x, a) \, dx \biggr) \end{equation} We can assume ...
user avatar
0 votes
0 answers
9 views

Randomness in iterative algorithm

Let $(H, \langle, \rangle)$ be a Hilbert space. take a closed and convex set $K \subset H$ and $f: K\times K \longrightarrow \mathbb{R}$. The equilibrium problem $EP(f,K)$ consists of finding $\...
user avatar
2 votes
0 answers
23 views

Is there an algorithm that can compute finite presentations for finitely presentable subgroups in a FP group with solvable word problem?

Given a group and its finite presentation $G=\langle A\mid R\rangle$, I want the following algorithm: Input: a finite set $W$ of words in $A\cup A^{-1}$ that generates a finitely presentable subgroup ...
user avatar
0 votes
0 answers
19 views

Converting recursive equation into matrices by using matrix exponentiation

This is an example of converting fibonacci function into matrices called matrix exponentiation method. Fibonacci sequence defines $$ f(1)=1 $$ $$ f(2)=1 $$ $$ f(x) = f(x-1) + f(x-2) $$ This recursive ...
user avatar
0 votes
1 answer
74 views

Find a simple path in given tree with minimum number of edges

Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length ...
user avatar
  • 1
2 votes
1 answer
31 views

Recursive algorithm complexity: Pedantic / Comprehensive proof

I'm trying to do a formal comprehensive proof of a certain recursive algorithm (Divide-and-conquer). My problem is that all resources I know always do some simplifications, and I don't manage to find ...
user avatar
0 votes
1 answer
39 views

Inductive proof for recursive function

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists over the alphabet. I've encountered the following function: $f([])=[]$ $f([x])=[x]$, for $x \in \Sigma$ $f(x:L)=f(L)$, for $x \in \Sigma$ ...
user avatar
  • 11
0 votes
0 answers
31 views

An algorithm to compute the eigenvalues of $A + B$ recursively

Is it posible to express a function $$ Eig_n(A, B) := \{ \text{The } n\text{ eigenvalues of the } n \times n \text{ matrix } A + B \}$$ The input of $Eig$ can be either described as the eigenvalues of ...
user avatar
  • 637
0 votes
1 answer
44 views

How to write the general solution for the recurrence relation: $x_{n+1} = x_n e ^ {\frac{1}{x_n}}$?

Consider the sequence $(x_n)_{n\geq0}$, with $x_0>0$ and satisfying the recurrence relation: $$x_{n+1} = x_n e ^ {\frac{1}{x_n}},$$ how you go about writing $x_n$ in terms of $x_0$, and the ...
user avatar
0 votes
1 answer
49 views

matlab coding - finding shortest path problem

Lately I've been trying to learn MATLAB and there's this project that have been assigned to me which I'm trying to do. the description of the project is as follows: we have a set of 100 points: $${(0,...
user avatar
  • 154
4 votes
1 answer
61 views

How many multiples of 7 contain a 7 in their decimal representation?

The first few multiples of $7$ that contain a $7$ in their decimal representation are $7, 70, 77, 147, 175, 217 ..$ (OEIS A121027). My question is how many such numbers exist below $n$: $$ f(n) = \...
user avatar
1 vote
2 answers
76 views

Solving recursive equation without Master's Theorem

Cheers, I am asked to find the time complexity of a recursive algorithm, which splits the starting problem on $\sqrt{n}$ subproblems, of size $\sqrt{n}$ each, and then combines the solution in linear ...
user avatar
0 votes
0 answers
38 views

Householder QR with column pivoting

In numerical linear algebra, we know how Householder QR can handle rank deficient matrices with column pivoting: which is essentially to choose the left-over columns with the maximum norm and use ...
user avatar
0 votes
0 answers
21 views

Is it possible to use a chunk of observations instead of one observation in Recursive Least Squares (RLS) at once?

Recursive Least Squares (RLS) by its structure reestimates coefficients iteratively utilizing one new observation in each iteration. Is it possible to use $n$ new observations in one iteration to ...
user avatar
1 vote
2 answers
30 views

Calculating the number of possible paths from an arbitrary starting point

I have a grid of size $n\times n$, where the origin is set at $(0,0)$ and the coordinates of the points on this grid, can only be positive. Let's say that we start at the point $(i,j)$. We can only go ...
user avatar
  • 532
1 vote
3 answers
93 views

solve the recurrence relation $a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $

Solve the recurrence relation $$a_n = 7a_{n-1} - 16a_{n-2} +12a_{n-3} + n4^n $$ With initial conditions: $a_0 = −2$ $a_1 = 0$ $a_2 = 5$ I solve the homogenous part like that: $$a_n - 7a_{n-1} + 16a_{...
user avatar
  • 11
0 votes
1 answer
53 views

variant of tower of hanoi

I am having a really hard time coming up with the answer for the variants of tower of hanoi. So the puzzle goes like this: there are $n$ disks and $n+1$ pegs. There is also an adjacency restriction ...
user avatar
0 votes
1 answer
96 views

Finding the number of pairs in an array such that all the numbers between the pair are strictly less than either number in pair

Question: Suppose we have an array $A$ of size $n$ all with distinct values. We define a pair $(a,b)$ with $a < b$ if for each $a < i < b$ we have that $A[i] < \min{\{A[a], A[b]\}}$. That ...
user avatar
1 vote
0 answers
14 views

Proof that a multiple recursive function generates an infinite set [closed]

if I have an example multiple recursive function like the following: $$f(x)\begin{cases}4x\ always\\\frac{x+1}{3}\ if\ mod(x+1, 3)=0\end{cases} $$ How can I proof that it generates (or it does not) a ...
user avatar
0 votes
1 answer
34 views

In how many ways can they be coloured so that two successive strips have different colours?

$n$ strips are to be coloured using three colours viz. red, blue and green. In how many ways can they be coloured so that no two consecutive strips are of same colour? My Attempt: Let $a_n$ be the ...
user avatar
  • 7,062
1 vote
1 answer
43 views

Proof for number of comparisons needed to find max two elements in an array

I am reading this post which explains the algorithm to compute the two maximum numbers in an array. In the second algorithm, we need to compute the number of comparisons that the algorithm makes. The ...
user avatar
1 vote
1 answer
47 views

Trying to Resolve One Recursion with Two Solutions

Background: I recently answered a question about the sequence of minimum Ford circles on each successive iteration here. I then asked myself the related question about the maximum circles on each ...
user avatar
  • 6,203
0 votes
0 answers
35 views

How to proof a greedy algorithm for return loans to bank

This problem was in my homework, now I'm preparing for exam but still couldn't understand it. We have $n$ loans, each loan has initial amount $R[i]$ and interest $a[i]$, and Monthly income $S.$ each ...
user avatar
  • 1
1 vote
2 answers
69 views

Looking for an algorithm

I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example: List of numbers: [1, ...
user avatar
0 votes
1 answer
21 views

Is the height of this recursive tree $\lceil \log _{2} n \rceil$?

I adapted the following code for a recursive binary cumulative sum function in Python: ...
user avatar
2 votes
1 answer
39 views

Recursively determine cubic spline coefficients

I am looking for a way to fit a cubic spline on previously recorded points without using matrices. The software is running on an embedded microcontroller which is low on RAM, so calculating my ...
user avatar
  • 123
0 votes
0 answers
16 views

Divide and Conquer: Statement Explanation

I have started reading Introduction to Algorithms by Thomas H Cormen. In Chapter 4, There is sentence that says Subproblems are not necessarily constrained to being a constant fraction of the original ...
user avatar
  • 11
0 votes
0 answers
27 views

Proposition of fast algorithm for graph with weights

If ever your Djkstra algorithms are in a situation where the max weight is much smaller than the number of vertices in your graph, try transforming each weight of size "x" into "x" ...
user avatar
1 vote
0 answers
101 views

Algorithm to find maximum sum over weighted overlapping intervals

Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
user avatar
  • 163
1 vote
2 answers
102 views

how can prove $n^n$ is primitive recursive

I try to prove $n^n$ is primitive recursive,first i try to releationate this proof with the proof of $x^y$, but in this case is different, because the base is not the same. So my attempt was to see ...
user avatar
1 vote
0 answers
167 views

Calculate all possible paths in graph

I have a number of graphs that look similar to this: Graph In this image, there are 4 levels and 4 node per level: Green is level 1, Blue is level 2, Pink is level 3 and Yellow is level 4. Graph - ...
user avatar
0 votes
0 answers
35 views

Find path between x pairs of vertices in undirected graph $G$

I am looking for the most efficient algorithm to find a path between every $x$ pair of nodes assuming $n$ total number of nodes in an undirected graph $G$ where $x$ is approx 1% of $n$. What are the ...
user avatar
3 votes
1 answer
113 views

What is the time complexity of $\sum_{i = 1}^n \mathcal{O}(n!)$?

Consider the following recurrence: \begin{equation*} T(n) = \begin{cases} \Theta(1) & \mbox{if $n = 1$}\\ n \cdot T(n - 1) + \Theta(n) & \mbox{otherwise} \\ \end{...
user avatar
3 votes
1 answer
66 views

Solve using substitution method solve $T(n) = T(n-1) + n$ by guessing $O(n)$

I'm still learning the substitution method and I'm a bit confused on how to find out whether my guess in fact correct or not Here's what I did so far: Induction goal: $T(n) ≤ cn$ Induction hypothesis:...
user avatar
2 votes
1 answer
89 views

Can't understand a recursive definition of reverse

reverse (x): get the reverse of a string x. For instance; reverse (aaabc) = cbaaa Ok, so I made this. $W_1 ∈ Σ$* and $W_2 ∈ Σ$* and $x ∈ Σ$ I guessed that $W_1$.$(W_2x)$ is a concatenation then $(W_2x)...
user avatar
0 votes
3 answers
62 views

Methods and knowledge needed for the conversion of $\sum$ and $\prod$ into non-iterative expressions

I think this might be a very broad question, but here it goes. I have made a formula, using a sigma function, to give the $n$th number in a recursive sequence. I'm trying to make it into a non-...
user avatar
1 vote
1 answer
42 views

prove $T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))+\theta(n) \\~\\ \Longrightarrow T(n)=O(n^{2})$

let $T(i)$ denote the worst-case running time of QuickSort algorithm on an input of size $i$. Then, the recurrence for the worst-case running time is given by: $$T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))...
user avatar
  • 329
1 vote
1 answer
56 views

Converting recursive equation into matrices

Here is example of converting fibonacci function into matrices. Fibonacci sequence defines $$ f(1)=1 $$ $$ f(2)=1 $$ $$ f(x) = f(x-1) + f(x-2) $$ It can be converted into matrix $$ \begin{bmatrix} 1 &...
user avatar
0 votes
0 answers
32 views

Proof of monotonicty of power functions

For all $x\in\mathbb R$ and $n\in\mathbb Z,$ we define the “nth power $x^n$” recursively by $x^0=1,$ $x^{n+1}=x^n \cdot x.$ a) prove that $f(x) = x^n$ is monotonic on $(-\infty, 0]$ and $[0, \infty).$ ...
user avatar
1 vote
1 answer
401 views

Why is "Turing machine makes no left move" decidable?

We know that every RE language is accepted by Turing machine. And emptiness, finiteness of every RE language is undecidable. My question is how I check decidability "the Turing machine makes move ...
user avatar
  • 1
1 vote
2 answers
161 views

Decidability of DCFL and Undecidability of CFL with respect to regularity

I synced with this Hendrik Jan's answer that to prove undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and ...
user avatar
0 votes
0 answers
21 views

Prove that divide and conquer for max sub array problem is O(n) if logs and exp are considered elementary(take one unit of time each)

I want to show that if logarithms and exponentials are considered as elementary that the divide and conquer algorithm is O(n) instead of O(n*log(n)) for the max sub array problem. I think it has ...
user avatar
  • 1
0 votes
0 answers
23 views

Divide and Conquer Algorithm comparison operator recursion

given a divide and conquer recursion \begin{equation} T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + N \end{equation} for $n \geq 2$ and $C_1 = 0$. I want to show that the explicit solution is ...
user avatar
  • 639
0 votes
1 answer
174 views

Divide and Conquer Algorithm for a Grouping Problem

I am trying to understand Divide and Conquer algorithm, I learnt it through the Skyline problem and I was able to understand that quite well, however the below problem is giving me troubles. I was ...
user avatar
0 votes
0 answers
12 views

Find a function 𝑓(𝑛) such that $𝑡_𝑛 ∈ Θ(𝑓(𝑛))$

I have a recurrence equation which is $t_n = -\frac{21}{2} 7^n + \frac{21}{2} 5^n + 10 n \cdot 5^n$. I need to find a function $f(n)$ such that $t_n \subset \Theta(f(n)) $. The problem here is ...
user avatar
2 votes
0 answers
176 views

Dijkstra's through certain sets of vertices in certain order

I'm stuck on coming up with an algorithm for the following scenario: Say you run a set of k errands in an area represented by a directed weighted graph G. Each vertex v is a place, and there is an ...
user avatar
  • 75

1
2 3 4 5
25