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

learn more… | top users | synonyms

3
votes
1answer
62 views

How to prove that calculating Ackermman function stops?

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ be Ackermann function. How to prove by structural induction ...
0
votes
0answers
139 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac n3)...
3
votes
1answer
2k views

Recursion tree T(n) = T(n/3) + T(2n/3) + cn

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac n3)...
1
vote
0answers
33 views

algorithm related to dyadic decomposition

Starting from an integer $n >0$, iterate the two operations of substracting one and dividing by $2$ (when the number is even) until $1$ is reached. Thus when the number is odd we can only substract ...
1
vote
0answers
92 views

Using FFT to compute DFT of a polynomial

i currently studying about FFT and DFT and we were given simple question: Use the recursive FFT to compute the DFT of this polynomial of '3' degree: $$-1\:+\:4x\:+\:3x^2$$. So, i go to this ...
0
votes
1answer
32 views

Can someone check my answers to this problem?

This is from Discrete Mathematics and its Applications Definition of recurrence relation from book From my understanding, compounded annually means that every year(annually) the account will ...
0
votes
1answer
37 views

Feasible method of grouping relations

This might be a bad question, I hope not so bad. Problem is I have a set of relations(millions), presumably two arrays hold two nodes(starting, and ending), which together forms a relation(edge). I ...
3
votes
0answers
134 views

Algorithm for Converting Rational Into Surreal Number

I'm writing a library in Haskell that represents the class of surreal numbers, which like many things can be read about here. I've run into a problem in converting between other classes of numbers (...
4
votes
0answers
110 views

How can I convert a recursive equation to a non-recursion one? [duplicate]

While I am aware of several other similar question which have been asked in the past, my mathematical education only extends through calculus, making them beyond my comprehension, and I believe this ...
5
votes
2answers
431 views

Characteristic equation. What is it?

Consider a recursive equation: $$ a_n = A a_ {n-1} + Ba_ {n-2} $$ And for this type of equation, there is characteristic equation: $ x ^ 2 = Ax + B $. What does exactly means that this equation is ...
1
vote
0answers
46 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than $2$ I should choose a special partitioning hyperplane for the divide and conquer algorithm to get $O(n \log n)$. I am confused because to choose this ...
1
vote
1answer
359 views

Give tight asymptotic bounds for the following recurrence. T(n) = 3T(n/3)+log n

Give tight asymptotic bounds for the following recurrence. Justify your answers by working out the details or by appealing to a case of the master theorem $$T(n) = 3T\left(\frac n3\right)+\log(n)$$ ...
4
votes
1answer
43 views

Finding all local $k$-maximums in sequence $a_1, a_2, \ldots a_n$.

For given sequence of numbers $a_1, a_2, \ldots, a_n$ we say that $a_i$ is $k$-local maximum, if $i > k$ and $a_i$ is largest of numbers $a_{i - k}, a_{i-k+1}, \ldots, a_i$. How can we find all $k$...
3
votes
1answer
71 views

Finding $m$ largest numbers from union of $k$ sorted lists $A_1, A_2, \ldots, A_k$

We are given $k$ sorted lists $A_1, A_2, \ldots A_k$ with corresponding sizes $n_1, n_2, \ldots n_k$. How can one find $m$ largest elements (numbers) from union of lists $A_1, A_2, \ldots, A_k$? We ...
2
votes
0answers
101 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set $...
3
votes
1answer
45 views

Question about recursive algorithm

I have following problem: $$f(n)=\frac{1}{1^2+1}+\frac{2}{2^2+1}+\frac{3}{3^2+1}+\cdots+\frac{n}{n^2+1}$$ Write recursive algorithm for $f(n)$ Prove that recursive algorithm is correct ...
3
votes
1answer
135 views

How can I recursively approximate a moving average and standard deviation?

Consider a sequence of measurements $(x_1, x_2, ...)$. Let $\mu_n$ be the $p$-period moving average defined by $$\mu_n = \frac{1}{p}\sum_{i=n-p+1}^nx_i$$ and $\sigma_n$ be the $p$-period moving ...
1
vote
2answers
383 views

Dynamic programming:Making a Change

I'm practicing problems on dynamic programming.The problem is as follows: You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so ...
1
vote
1answer
27 views

Proof by induction for a recursive function f

Consider the function $\operatorname{f}: \Bbb N \to \Bbb N$ defined recursively as follows: 1) Base case: $\operatorname{f}(0) = 0$ 2) Recursive case: $\operatorname{f}(x) = \operatorname{f}(x-1)+4$,...
0
votes
1answer
42 views

Proof by induction for a recursive function

Really having a tough time doing this question: Consider the function $\operatorname{f}: \Bbb N \to \Bbb N$ defined recursively as follows: 1) Base case: $\operatorname{f}(0) = 0$ 2) Recursive case:...
0
votes
3answers
1k views

Counting arrays with gcd 1

I want to calculate the number of arrays of size $N$, such that for each of it's element $A_i, 1 \leq A_i \leq M$ holds, and gcd of elements of array is 1. Constraints: $1 \leq A_i \leq M$ and $A_i$ ...
1
vote
4answers
382 views

Prove that the Fibonacci recursion diverges

I have this sequence with $ n \in \mathbb{N} $ $ f(1) = f(2) = 1 $ and $ f(n) = f(n-1) + f(n-2) $ for $n \ge 3$ I think this sequence is bounded below and unbounded above. So it's clear that this ...
0
votes
3answers
66 views

Constructing a recursive sequence that converges to sqrt 17

One of the problems that we have for abstract math is the following: Using the recursive sequence definition, construct a sequence that converges to $\sqrt{17}$. It is my understanding that the ...
4
votes
1answer
146 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-219}-64a_{n-3}+k $$
0
votes
1answer
48 views

Explicit (General) formula for recursive definition.

I am given $a_n=3a_{n-1}+4^n$, $n=1,2,3,....$ and $a_0=1$. First four terms: $$ \begin{align} a_1&=3.1+4^1=3+4=7\\ a_2&=3.7 + 4^2 = 21 + 16 = 37 \\ a_3&=3.37 + 4^3 = 111 + 64 = 175\\ ...
0
votes
1answer
49 views

Solving time complexity of merge sort

I was asked to prove that the time complexity of merge sort is $ O(log_2n)$ but I cannot find a way to continue my method. Any help? $T(n)=2T(\frac{n}{2} )+n$ $T(n)= 2[2T(\frac{n}{4})+n] +n = 4T(\...
0
votes
1answer
32 views

Log property in proof of Master theorem

The family of recurrence considered is of the form $$ T(n) = aT(n/b) + n^c $$ $a,b,c$ are integers. One case of master theorem states: if $c< log_b a$, then $T(n) = \Theta(n^{log_b a}) $. I have ...
4
votes
2answers
141 views

Finding the convergent value of a recursion similar to Arithmetic-Geometric Mean recursion

The sequence is defined as follows : Start : $(x_0,y_0)$ with $ 0 < x_0 < y_0 $ Step : $x_{n+1} = \frac {x_n+y_n} {2}$ , $y_{n+1}= \sqrt{x_{n+1}y_n} $ Find $\lim_{n\to \infty}(x_n,y_n)$ . ...
2
votes
4answers
101 views

Find exact closed form of recurrence $g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$ for $ n \geq 2$

$g(0) = 0, g(1) = 3, g(n) = g(n − 1) + 2g(n − 2)$ for $n \geq 2$ Our lecture notes suggest us to work backwards until you get the first term, i.e. $g(1)$ I am not quite sure how that works as the ...
1
vote
0answers
61 views

Help me generalize what this divisor transform does.

I have an algorithm which takes as input the series expansion of: $$\frac{-(1 + ax(-2 + x + ax))}{-1 + ax} \tag 1$$ or expressed differently: $$\left\{a^0,(-a)^1,a^1,a^2,a^3,a^4,a^5,a^6,a^7\right\}$...
1
vote
0answers
164 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} \...
0
votes
1answer
69 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...
1
vote
3answers
25 views

running time of an algorithm

I am trying to prove an algorithm with input size $n$ satisties the recurence relation (for $n>=1$) $T(n) = T(n-1)+n$ and an initial condition of $T(1)=1$ has running time in $Θ(n^2$). By using ...
1
vote
0answers
31 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 \...
0
votes
1answer
62 views

$T(n)=T(n-1)+O(\log n)$ is $T(n)=O(n^2)$ or $T(n)=O(n \log n)$

I have this Recurrence relation: $T(n)=T(n-1)+O(\log n)$ What is the solution? $T(n)=O(n^2)$ or $T(n)=O(n \log n)$ What I did is: I assume that $T(n)\le O(n^2)$ And that's bring me to $O(n^2)$, ...
2
votes
2answers
173 views

Towers of Hanoi Starting From Initial (Legal) Configuration?

I was recently asked in an interview how an algorithm for solving the classic Towers of Hanoi problem would differ if you were given an initial (legal) configuration of the towers, and had to start ...
1
vote
3answers
70 views

recursive to explicit sequence

I am trying to find the explicit formula for the following recursion: $$a_{1}=3,\quad a_{n}=3- \frac{1}{a_{n-1}},\quad n \in \mathbb N,n>1$$ I tried in many ways but I cannot find any ...
1
vote
1answer
28 views

Algorithm Running Time

Given an algorithm with a running time $$T(n)=5T(n/2)+n^2$$ So the number of nodes at a depth $i$ would be: $5^i$ The input size for each node at $i$ would be: $n/2^i$ Agreed. Then it states that ...
5
votes
1answer
555 views

How many distinct ways to climb stairs in 1 or 2 steps at a time? (Fibonacci puzzle)

There is a very interesting puzzle for fibonacci sequence ...
0
votes
1answer
38 views

How to find if an array has at least 10 unique integers in $O(\log n)$?

I am given a sorted array of integers. I want to find out if the array has at least 10 unique integers. I know this can easily be done with an algorithm that runs in $O(n)$ simply by going through ...
1
vote
0answers
41 views

Finding the explicit form of the recursive function $P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor$

I'm trying to find the explicit form of the recursive function $$P_{1(n)}=\left\lceil\frac12P_{1(n-1)}\right\rceil+\left\lfloor\frac12P_{2(n-1)}\right\rfloor\;.$$ First, let me explain what this ...
2
votes
5answers
168 views

How to give a good guess to the recurrence relation problem [duplicate]

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
1
vote
2answers
54 views

Optimal Number of White Balls

There are C containers, B black balls and infinite number of white balls. Each container should have at least one ball. Each of the containers may contain any number of black and white balls. Action ...
1
vote
0answers
47 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ R_{n+...
1
vote
1answer
382 views

Generate all permutations of a string containing repeated characters

I was writing a program to print all the permutations of a string. I came up with the following: ...
0
votes
0answers
26 views

Binary Search when no “fixed” answer…? (Font Sizing)

So I'm trying to figure out how best to implement a binary search algorithm to find the "optimal" font size for a piece of text to fit into a given space, to the nearest 0.5pt. My understanding is ...
0
votes
1answer
22 views

Recurence Problem. - Solve either by substitution or Expansion

Function T(n) is defined by the following recurrence relation: $$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$ $$ T(0)=1 $$ How would I Solve by substitution and/or Expansion? Note: ...
1
vote
1answer
111 views

Using Extended Euclidean Algorithm for $85$ and $45$

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have no ...
1
vote
2answers
61 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
1
vote
1answer
363 views

Solving recurrence equations with repeated substitution?

Say we have a recurrence equation as $$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$ Would the first substitution be like this? $$\...