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

learn more… | top users | synonyms

1
vote
2answers
43 views

Calculate a recursive equation in terms of theta

I am struggling with the following equation for one week! Please help me solve it. $$T(n)=T(\frac{n}{2})+\frac{n}{logn}$$ So far, I have come to the equation $T(n)=\Sigma \frac{2^x}{x}$
0
votes
1answer
69 views

Quadratic Map Solution

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
0
votes
0answers
18 views

How to formally describe indirect partial derivatives with two paths

Assume I have two functions like this: $y = \frac{1}{2}(o-x)^2\\o = kx$ Now, I want to calculate $\frac{\partial y}{\partial x}$ using the chain rule, i.e. like this: $\frac{\partial y}{\partial x} ...
2
votes
1answer
184 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
1
vote
1answer
46 views

Transfer a program into a logarithm formula

I have been thinking what is the math formula for the piece of code I wrote below. Assume there are B, D and F three positive integers, and D is smaller than F. Given D and F, the value of B would be ...
2
votes
0answers
25 views

Recursive and Recusively enumerable

{1^n | n finite integer and >1}, is this language recursive? I'm not sure how to prove that a language is recursive, I only know that there should be a TM that accepts any finite input and then ...
0
votes
1answer
25 views

Recursive Algorithm Analysis

$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ...
0
votes
0answers
61 views

Inventory Control using Dynamic Programming

I am trying to solve a traditional inventory control stochastic dynamic programming problem where \begin{align} x_{k+1} &= x_k + u_k - w_k\\ w_{N-1} &= \begin{cases} 0 &\text{w.p. } ...
1
vote
1answer
22 views

What is the link between the quotient and the Bézout coefficients in the Extended Euclidean Algorithm?

Here is an image from the wikipedia page of the EEA for working out the Bézout coefficients for 240·sk + 46·tk = rk where rk = GCD(240,183): What I am trying to work out is what si and ti ...
0
votes
0answers
31 views

How to define this f(n) (something about recursion)?

Consider this: $$best(n)=\begin{cases}1 & \text n=1,\\2*best(n-i)+2^i-1 & \text otherwise,1<=i<n\end{cases}$$ That is, when $n>1$, for each $i$ among $[1,n)$, there must be at least ...
2
votes
1answer
90 views

The Matrix Inversion Lemma: the General Case

I find it is hard to understand the application senario of the Matrix Inversion Lemma in non-special cases. Suppose I already computed $A^{-1}$ and want to find $\left(A+UCV \right)^{-1}$. The Matrix ...
0
votes
0answers
48 views

Why can I not generalize O(n^log5) for squaring matrice of size n

I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
0
votes
1answer
24 views

Recursively calculate grand total

Starting January, I have a value of 2.5. Each month I add 2.5. I believe that I = Prt will tell me the final value in December, but I need the running total. Ex: ...
1
vote
1answer
29 views

Multiplication cannot be obtained from zero, successor, and identity by composition without recursion

The task is to show that multiplication cannot be obtained by zero, successor, or identity functions by composition without using recursion at least twice. I'm primarily confused because it doesn't ...
0
votes
1answer
93 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
1
vote
1answer
65 views

Find coefficients of polynomial that has zeros at certain points

Given a list of values z0, z1, ..., zn-1 (possibly with repetitions), show how to find the coefficients of a polynomial P(x) of degree-bound n + 1 that has zeros only at z0, z1, ..., zn-1 (possibly ...
1
vote
0answers
18 views

Determining the optimally scoring move on a probabilistically represented 2D grid in real time

I'm posting this to StackOverflow, cstheory.stackexchange.com, and math.stackexchange.com because I'm not really sure where it fits best. I hope that's OK. I have a 2D grid (size varies per map, ...
1
vote
3answers
149 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
4
votes
5answers
769 views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
0
votes
3answers
33 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
0
votes
1answer
29 views

Time complexity of indirect recursion

How to find the complexity of an the given algorithm: Algorithm f(int n) { if(n==1)return(1); else { f(n-1)+g(n-1); } } Algorithm g(int n) { ...
0
votes
0answers
134 views

Find all possible paths in a Matrix

I'm looking for algorithms to find all paths in a 4 x 4 matrix. The rules are as follows You can move in any direction (up, down, left, right, and diagonally) The next square in the path must be a ...
2
votes
1answer
75 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
1
vote
1answer
112 views

How to show this algorithm on positive semidefinite matrices converges to a global maximum determinant

I'm dealing with an algorithm which is supposed to converge to the maximum determinant of certain positive semidefinite matrices. The problem is that we have such a matrix, and we vary certain ...
4
votes
3answers
159 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
1
vote
1answer
89 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
1
vote
1answer
87 views

What's a useful recurrence relation for $(2n)!$ in terms of $n!$?

I want to make an algorithm for $n!$ which will divide the number in half and call the algorithm again until n is so close to $0$ that a value of $1$ can be safely returned, and use the value of each ...
1
vote
1answer
61 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
1
vote
4answers
39 views

Identity for this recursive relation with multiple terms

I have a recursive relation algorithm which is defined as follows: $$F_n = 3(F_{n-1} - F_{n-2}) + F_{n-3}$$ $$F_0 = 0$$ $$F_1 = 1$$ $$F_2 = 4$$ From calculating the first few values, I know this is ...
2
votes
3answers
92 views

Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
2
votes
1answer
56 views

Please explain why the below algorithm has n*m subproblems rather than 2(n+m-1) subprobems.

I am providing the solution as well which I found on the web. I don't understand why it says at the end that there are n*m subproblems. Question: For bit strings X = x1 . . . xm, Y = y1 . . . yn ...
0
votes
0answers
29 views

Algorithms Analysis: Double Recursion and how to Analyze?

This is quite a simple question, but maybe not so simple to think about. What if I have an algorithm which has "stacked" recursion, such as this? Func(n): ...
0
votes
0answers
49 views

Tight bounds for the number “2 in a hexagon” wanted (Steinhaus-Moser-Notation)

The Steinhaus-Moser-function is defined in the following way : $$M(n,1,3) = n^n$$ $$M(n,1,p+1) = M(n,n,p)$$ for all $p\ge3$ $$M(n,m+1,p) = M(M(n,1,p),m,p)$$ for all $p\ge3$ and $m\ge1$ The ...
1
vote
0answers
21 views

Is there a method to calculate Mahalanobis distance incrementally?

By incrementally (or recursively) I mean to update the pool/group of values/vectors as soon as more vectors are available without having to recompute the entire covariance and inverse matrices. I ...
0
votes
1answer
33 views

Reccurence relation

Closed form of $\ nT_n = 3(n-1)T_{n-1} + 1, n \ge 1$ I've tried calculating some terms, and looking it up on wolframalpha, it sais the generating function is $\frac{exp(x)}{1-3x}$. Where do i start? ...
1
vote
1answer
123 views

Proving by induction that a palindrome contains an even number of $b$s and $c$s

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these ...
0
votes
1answer
42 views

A recursive definition of palidrome over {a,b}

Can someone please explain how this recursive definition produces palindromes over $\{a,b\}$? For example, how can we get the string $abaaaba$ as a valid string? Rule 1: $\epsilon$, $a$, and $b$ are ...
1
vote
1answer
40 views

A Shifted Sorted Array - finding the shift

I was given a problem concerning a sorted array that is shifted by some "number of spaces", k. For example, take the sorted array $1, 2, 3, 4, 5 ,6$ It is shifted 2 spaces, we get: $5, 6, 1, 2, 3 ...
2
votes
2answers
105 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
1
vote
1answer
28 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
0
votes
3answers
42 views

Recursive relation

Sequence defined by recursive relation $a_{n+1}=\alpha a_n +2$ Prove that if $\left|\alpha\right|\lt1,$ the sequence has a limit independent of $a_1$. I have seen this work for the case when ...
0
votes
0answers
339 views

Algorithm to Generate Number with 0 and 9 [duplicate]

You are given an integer N. Can you find the least positive integer X made up of only 9’s and 0’s such that X is a multiple of N? Is there any Algorithm to generate the least number. Thank you.
4
votes
3answers
157 views

Recursion with Random number?

function foo(n) if n = 1 then return 1 else return foo(rand(1, n)) end if end function If ...
0
votes
1answer
183 views

how to prove the convergence of fixed point iteration algorithm

Please refer to the below algorithm: Above two steps can be rewritten as, \begin{equation} x(k+1)=\arccos\bigg( -\frac{1}{2(Dr^{\frac {|\sin(2x(k)+\theta)|}{M\sin ...
0
votes
3answers
151 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
0
votes
1answer
34 views

Recursion equation

$$f_k = \sum\limits_{k = 1}^{k-1} (f_i + f_{k - i}), \text{ when } k \ge 2, \text{ and } f_1 = 1$$ Find/guess a closed form for $f_k$, i.e. a formula in only the variable $k$; and prove the ...
2
votes
2answers
106 views

Tiny Planet Algorithm?

So I've recently been looking at the Tiny Planet images. I've been googling a few things to try and find out how images are converted from normal to a tiny planet. Some phone apps, as well as ...
0
votes
2answers
84 views

Repertoire Method. How to know when equations are valid

I'm trying to work a few examples from the Repertoire Method from the Book Concrete Mathematics. I'm working through the following recurrence: $f(0) = 1$ $f(n) = 2f(n-1) + n$ Which I generalized ...
1
vote
0answers
41 views

Is undecidability of arithmetic a corollary of Tarski undefinability theorem?

Arithmetic is undecidable, in other words the set of Godel numbers of theorems of arithmetic is not recursive, and so there is no algorithm/ recursive function to decide if a statement is provable or ...
0
votes
0answers
77 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.