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

learn more… | top users | synonyms

2
votes
1answer
76 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
115 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
96 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
92 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
94 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
30 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
50 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
34 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
127 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
44 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
41 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
29 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
159 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
200 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
159 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
108 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
86 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
42 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
93 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.
1
vote
0answers
119 views

Sequential Algorithm to generate Fractal (Koch's snowflake)

As part of an assignment I had developed a sequential algorithm to generate a Koch's snowflake. Algorithm I have encountered so far have been recursive and iterations generate closer approximations. ...
0
votes
0answers
87 views

Algorithm for reversion of power series?

Is this an algorithm for power series reversion? As input I give the alternating reciprocals of the factorial numbers: ...
0
votes
0answers
31 views

Understanding the difference between two similar looking recurrences.

Looking at this recurrence, $f(n) = f(n/2) + nlgn$ The book claims we can conclude that $f(n) = \Omega(nlgn)$ since $f(n/2)>0$. Furthermore, for a sufficiently large $n: lgn \le n^{\epsilon}$ for ...
5
votes
1answer
97 views

Flip all to zero

I have a square grid of size $N$, with rows numbered from $0$ to $N - 1$ starting from the top and columns numbered from $0$ to $N - 1$ starting from the left. A cell $(u, v)$ refers to the cell that ...
1
vote
0answers
131 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
4
votes
3answers
69 views

Recursion, multiplication and exponential

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
3
votes
1answer
39 views

Finding a recursive definition and computing $B(10)$

For $n \geq 1$, let $B(n)$ be the number of ways to express $n$ as the sum of $1$s and $2$s, taking order into account. Thus $B(4) = 5$ because $4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = ...
0
votes
2answers
34 views

Number of ways to arrange n identical stones into piles

Given, there are n stones which are identical. How many ways can the stones be arranged into piles. Suppose if n=4 , we can make one pile with 4 stones or 2 piles with 3,1 or 2,2 or 3 piles with 1,1,2 ...
2
votes
1answer
89 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
1
vote
1answer
86 views

Inductive Definition of regular expression

Give an inductive definition of regular expressions that do not use the star operator. Prove by induction on this definition that every such expression denotes a finite language not containing lambda. ...
1
vote
0answers
46 views

How to derive recursive equation for expected discounted utility function?

I am trying to mathematically represent expected discounted utilities when the length of a lifetime is uncertain. $V_0$ is the expected discounted utility at $t=0$ and can be represented as such: ...
0
votes
1answer
59 views

how do you rewrite a recursive formula to find its roots

Let $(x_n)$ be the sequence defined by $x_1=2$ and the recursive formula $x_{n+1} = \frac12 + \sqrt{x_n}$. Rewrite the recursive formula in the form $$ x_n - x_{n+1} = ax_{n+1}^2 + bx_{n+1} + c$$ ...
2
votes
4answers
118 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
0
votes
1answer
90 views

Discrete Math: “Drop Zero in Bitstring” Recursive function

how do i define “dropzeros” of a bitstring as the result of dropping each 0 from the bitstring. ex) dropzeros of 11 is 11. The dropzeros of 1101 is 111. The dropzeros of 00 is the empty string. Let’s ...
0
votes
1answer
97 views

Discrete Math: Recursive Functions

You are given the following recursive definition defining a set of strings. 1∈S; x∈S → x11∈S. What are the 4 shortest members of the set? What does x11∈S mean?
1
vote
0answers
143 views

Help with find recurrence relation running time.

Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. ...
0
votes
1answer
54 views

How to solve recursive function

I've recently been doing some limits with circuits and such, and I came up with the following equation, $R$ being a constant: $$f(x) = \frac{f(x-1)*R}{R+f(x-1)}+R$$ with $f(1)=2$. I know that this ...
2
votes
0answers
76 views

Interesting Recursive Continued Fraction Limit

I was messing around with recursive functions the other day and came up with something that could be interesting: Definition of $\bar{\Xi}(n)$:\ Let $\Xi ...
3
votes
2answers
147 views

Google Question: Number of ways to select sets such that n is pure

Consider a subset $S$ of positive integers. A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, ...
0
votes
1answer
119 views

Recurrence Relation for Optimal Card Game Score

I have the following problem where Alice and Bob decide to play a simple card game. At the beginning of the game, $n$ cards are dealt face up in a long row. Each card is worth a different number of ...
2
votes
1answer
64 views

Recurrence relation of an integral [closed]

$$ y_n = \int_0^1 \frac{x^n}{x+5} dx,\ \ n=0,1,2,...,\infty $$ What is the recurrence relation between $y_n, y_{n-1}$ ? Could you provide me a methodology on how to proceed with this?
1
vote
3answers
118 views

Finding the limit of the recursive sequence $r_{n+1} = \sqrt{2 + r_n}$

In the example I am given, I am told that $r_n$ is defined as: $$ r_n = \begin{cases} r_0 = \sqrt{2} \\ r_{n + 1} = \sqrt{2 + r_n} \\ \end{cases} $$ I was told to calculate ...