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

learn more… | top users | synonyms

2
votes
0answers
17 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
1
vote
0answers
45 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, ...
0
votes
1answer
20 views

how to determine maximum length of chain of tail-to-head connections in a given word list

Given a finite set of words, I wish to to write an algorithm which will create a chain of words, where the tail (last letter) of a word n will be the same as the ...
0
votes
2answers
37 views

Converting from base 2 to base 10 through division [closed]

I'm having hard time because of this exercise, I have to implement an algorithm that repeatedly, through continuos divisions, from the remaining of the divisions I can find(looking backward the ...
0
votes
0answers
28 views

Is it true that Ackermann's function cannot be implemented without recursion? [duplicate]

Yesterday I got sucked into a bingewatch of Computerphile's and Numberphile's videos on youtube. In particular I ended up watching some on Ackermann's function. While I knew already this function (and ...
0
votes
2answers
40 views

Proving that this algorithm distributes a quantity as expected

Background (non-essential) Let $Q$ be an integer quantity (of say, marbles) to be distributed into $n$ buckets ($B_1$ ... $B_n$) according to weights. Let $w_1$ ... $w_n$ be the non-negative weights, ...
0
votes
1answer
31 views

Complexity of subset-generation algorithm

I'm trying to calculate the computational complexity of an algorithm which generates the power set of a set of items. The algorithm works using the recursive formula of the binomial coefficient ...
0
votes
2answers
104 views

Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...
0
votes
0answers
19 views

For graphs in a recursive graph class: Does m = O(n) hold?

For recursive k-terminal Graph classes - for example definied in this paper - is it true that |E| = O(|V|)? If so, I would be very grateful for a reference! Thanks!
0
votes
0answers
14 views

Formula for running-time complexity

I'm regarding a stochastic process $(X_t)$of which the mean starts at $O(n)$ and is reduced by the factor $(1-r)$ in each step with $r = \Omega (1/n^9)$, so $$E(X_{t+1}) \leq E(X_t) (1-r) .$$ Now it ...
0
votes
0answers
28 views

recursion $t(n)=\sqrt{2} \times \frac{tn}{2} +\log{n}$

I tried substituting $m=\log{n}$ $t(2^n)=\sqrt{2} \times \frac{t2^n}{2}+m t(m)= \sqrt(2) \times \frac{tm}{2}+m$ From here I got $\log {n}$ But with induction I proofed its $\sqrt {n}$
0
votes
1answer
34 views

Is there an algorithm to generate these specific sequences of numbers?

f(1) = [1] f(2) = [2,1,1] f(3) = [3,2,1,1,2,1,1] f(4) = [4,3,2,1,1,2,1,1,3,2,1,1,2,1,1] ... f(n) = ... The lengths of the lists f(n) are $2^n - 1$ (Mersenne ...
0
votes
1answer
48 views

Values of the Sudan function

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the ...
1
vote
0answers
21 views

FFT procedure for evaluationg a polynomial at $N$ Fourier points

The following is the recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points. Algorithm (FFT - fast Fourier transform). Input arguments. $ \ ...
0
votes
1answer
78 views

How can I solve this recurrence problem?

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
0
votes
1answer
26 views

Show that running time of Quick Sort is $\mathcal O(n^2)$ when array contains distinct elements and is sorted in descending order

I'm trying to study running time for various algorithms. Now I have QuickSort. How exactly is the running time of an algorithm calculated, I know how quick sort works and the Asymptontic notations. I ...
0
votes
1answer
17 views

Understanding recursive function for finding GCF of 2 numbers

So I get how this code works, but I don't understanding why it works. The function assumes input num1 > num2. Algorithms are hard for me to grasp, so please explain to me like I'm five. Heres the ...
0
votes
0answers
10 views

Bounded Knapsackproblem Formula DP

I knew how the binary Knapsack works with Dynamic Programming. But, now I am interested. How does the recursive formula look like if I allow n€{0,1,2} of the same item to be in the Knapsack? The only ...
2
votes
0answers
39 views

Solving this recurrence relation representing constant-power loads on a resistive cable

Given the following: $$\begin{align} v_n&=v_{n-1}-r\sum_{i=n}^m \frac p{v_i}\\ v_0&=V \end{align}$$ where: $$\begin{align} m\ge n\ge 0\;&:\;m,\,n\in\mathbb {N_0}\\ ...
1
vote
0answers
20 views

Sources and sinks for parabolic PDE algorithm

I am given a very basic fortran program (View here) and asked 1st to investigate its accuracy and stability, for various values of $ \Delta t $ and lattice spacings. The program is an implementation ...
0
votes
1answer
32 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
0
votes
3answers
33 views

A set S is defined recursively by

A set S is defined recursively by Basis step: $0 \in S$ Recursive step: if $a \in S$, then $a + 3 \in S$ and $a + 5 \in S$. Determine the set $S \cap \{ a \in \mathbb Z \mid 0 < a < 12 \}$. ...
-3
votes
2answers
51 views

Probability of arriving H before A [closed]

I m in the point X. I m 2 blocks up from a point A and 3 blocks down from my home H. Every time I walk one block i drop a coin. H . . . X . . A If the coin is face I go one block up and if it is ...
2
votes
2answers
68 views

Most efficient algorithm to distribute n n-bit strings among n people

We are given $n$ people, whom we identify with the elements of $[n]=\{1,\ldots,n\}$. We are also given a finite collection $\mathcal{K}$ of subsets of $[n]$. The problem is to (efficiently) ...
4
votes
4answers
1k views

A 3rd grade math problem: fill in blanks with numbers to obtain a valid equation

Even though this is a 3rd-grade math problem, people found it extremely hard. Any people have a solution, or algorithm is welcome. I'll try make a program base on the algorithm and see if it's ...
7
votes
1answer
149 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
3
votes
1answer
55 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
0
votes
1answer
25 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
1answer
34 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
1answer
37 views

Sequence who converges to $\sqrt{a}$ for every $a\geq0$

If we have: $$x_n=\left\lbrace \begin{matrix} b\in\mathbb{R}\setminus \{0\} & ,n=1 \\ \dfrac{a+x_{n-1}^2}{2x_{n-1}} & , n>1\end{matrix} \right.$$ Then, is easy to prove that $(x_n)\to ...
2
votes
1answer
63 views

Solving $T(n) = 3T(n-1)$

How is the constant before the $T$ important to the result from $T(n)$ I know that \begin{equation*} T(n) = T(n-1) + 3 \Rightarrow \theta(n)~\text{and}~T(n) = T(n-1) + n \Rightarrow \theta(n^2) ...
1
vote
1answer
95 views

Struggling with difference between greedy and naive but optimal algorithms? (Graph theory)

I've been thinking about the following problem for quite a while and tried multiple solutions, but I'm having difficulty telling the difference between a greedy algorithm and an inefficient naive ...
0
votes
1answer
31 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
2
votes
1answer
47 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
0
votes
0answers
13 views

recurrence tree final step - binary search

Starting with the base case and recursive case run times as follows: 􏰀 t(N) = 1 , if N = 1 t(N)= 1+t(N/2) ,ifN > 1 At the end of my tree I have ...
1
vote
3answers
47 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
1
vote
0answers
68 views

Coppersmith-Winograd algorithm

I'm interested in algorithms to compute matrix multiplications. Is the Coppersmith-Winograd algorithm similar to the Strassen algorithm ? I have two other questions: 1) Are the multiplications done ...
0
votes
0answers
13 views

Formula for a recursive function

Given the recursive function $T: \mathbb{N}_0 \to \mathbb{R}_+$ $$T(n) ≤ max_{1 ≤ k ≤ n - 1}\{T(k-1) + T(n - k) + c n^2\}$$ with c > 0 constant, I want to determine an absolute formula to quickly ...
0
votes
1answer
24 views

Recursive solution to “Number of subsets of a set without 3 following numbers”

so I got the following problem: For a given natural n number, let A be the set A={1,2,...,n} I need to provide a recursive solution that will return the number of possible subsets that doesn't ...
0
votes
1answer
23 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
0
votes
2answers
26 views

Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
1
vote
0answers
20 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
3
votes
1answer
48 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
25 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
2
votes
0answers
116 views

How to find a enclosed envelope with maximum points among a cloud of spheres? [ Concave Hull ]

I have a questions regarding the selection of the outer points (i.e. sphere center), among a collection of many spheres in 2D/3D space. The outer points is that when all of these points are ...
0
votes
0answers
18 views

Spin-off of Scheduling Weighted Interval Problem

I'm trying to solve a problem in which, given a + sign shaped area of land (with no width) and a list of contiguous sections of the land (segments, T-shapes, smaller + shapes, etc), each with an ...
3
votes
1answer
36 views

Proving a recursive algorithm on a set is true

If I have an algorithm that returns the entry of a set with the largest value, how do I prove the algorithm is true mathematically? (I know I could just write tests for it.) I understand how to use ...
0
votes
0answers
19 views

Recursive relationship for Peano Baker Series

The Peano Baker Series is a integral has the following form $$\varPhi(h,0)=I+\intop_0^h G(t_{1}) \, dt_1 + \intop_0^h G(t_1) \intop_0^{t_{1}} G(t_2) \, dt_2 \, dt_1 + \intop_0^h G(t_1) ...
0
votes
1answer
34 views

Find a shortest way between nodes in graph

I have a next structure : Each node in graph may have more than 2 links. I want to find a shortest way with node 1 and 13. ...
-3
votes
1answer
51 views

Edited-How can I solve polynomial recurrences like $f(n+1)=\frac{2f(n)}{f(n)+1}$

Can anybody tell me the systematic way of solving this recurrence. $$f(n+1)=\frac{2f(n)}{f(n)+1}$$ I looked over the internet, but could not find the answer. Thanks {Edit- I am sorry, previously I ...