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

learn more… | top users | synonyms

0
votes
0answers
93 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
32 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
99 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
70 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
95 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
47 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
119 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
92 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
100 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
147 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
56 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
148 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
121 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
121 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 ...
0
votes
1answer
59 views

Give a randomized algorithm to find the median that has an expected number of comparisons = 2n + o(n)

Any help would be very much appreciated. I'm aware of 2 types of algorithms: "Median of the medians" and one using guards like here: http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture9.pdf ...
1
vote
1answer
118 views

Solving nested summation $\sum_{i=0}^{n-1} \sum_{j=i}^{n-1}p(A_i)p(B_j) $

I am having trouble solving the following nested summation: $$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1}p(A_i)p(B_j) $$ where $p(A_i) = \frac{1}{n}$, and $n$ is a constant (length of an array). Same goes for ...
0
votes
1answer
35 views

Find another recursive algorithm that is equal to a series

I have the following sequence: $$ y_n = \int_0^1 \frac{x^n}{x+5}\,dx, n = 0,1,\dots $$ Now I have the following recursive algorithm which is equal to the sequence: $$ y_0 = \log{6} - \log{5} $$ $$ ...
0
votes
2answers
88 views

How to prove that a series is equal to a recursive algorithm

I have the following sequence: $$ y_n = \int_0^1 \frac{x^n}{x+5}\,dx, n = 0,1,\dots $$ Now I have the following recursive algorithm: $$ y_0 = \log{6} - \log{5} $$ $$ y_n = \frac{1}{n} - 5y_{n-1}, n ...
1
vote
2answers
71 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
2
votes
1answer
93 views

What is the bound of: $T(n) = T(n-2) + (n)log(n)$?

I am given the following recurrence relationship: $\ T(n) = T(n-2) + nlog(n)\\ T(1) = T(0) = constant$, I need to find the order for the recurrence. So, using the iterative methodology, what I ...
1
vote
1answer
54 views

How does my textbook come up with this statement? I don't believe it to be true.

My textbook (Introduction to Algorithms) states the following: When polynomially comparing $n^\epsilon$ and $lgn$, it states that $n^\epsilon$ is polynomially greater for any positive $\epsilon$. ...
1
vote
3answers
79 views

Where is the value of the variable $\epsilon$ obtained in the following explanation my professor gave?

My professor gave us this explanation from the textbook Introduction to Algorithms regarding the Master Method/Theorem: As a first example, consider $$T(n)=9T(n/3)+n.$$ For this recurrence, we ...
0
votes
1answer
218 views

Big Oh Notation for a Recursive Algorithm

I have a question that I'm unsure of: Express the complexity of the following method using big-O notation. You must explain how you arrived at your answer. What value is returned by the call ...
0
votes
1answer
106 views

An alternative to the Master Theorem?

I've been reading up on the Master Theorem (used for identifying the worst case run times of a certain class of recursive functions [ the divide and conquer type] ). I looked at the Wikipedia entry ...
0
votes
2answers
128 views

Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
1
vote
2answers
60 views

How does my professor come up with the recursive case in this algorithm analysis?

My professor gave us the following explanation for the recursive algorithm for finding the permutations of a set of numbers: When he has (T(m+1), n-1)) where does that come from? Why is it m+1 ...
0
votes
0answers
69 views

How is the algorithm for recursively printing permutations of a set of numbers this equation our professor gave us?

I'm having a great amount of trouble understanding where my prof got $T(m, n) = n(T(m+1, n-1) + m+1 + n)$ if $n > 1$ as the recursive formula for the algorithm for recursively printing the ...
0
votes
1answer
25 views

Defining a recursive function $f$ on $\{a, b\}$*

I would need some help on how I can define a recursive function $f$ on $\{a, b\}$* Define a recursive function $f$ on $\{a, b\}$* which replaces any $a$ with $b$ and vice versa, for example, ...
0
votes
2answers
58 views

I need some help on solving a recursive function question

I'm working on a recursive function task which i'm a bit stuck at. I've tried to google it on how I can solve this task, but with no luck Here is the task: Provide a recursive function $r$ on ...
0
votes
1answer
73 views

How can I solve this recursion function task?

I really need help on this task. Im stuck at it and I really would appreciate your help here. Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) = kkigol$ and ...
1
vote
3answers
51 views

How does my professor go from this logarithm to the following one of a different base?

I don't understand on the second last line how my professor goes from $2^{log_3(n)} = n^{log_3(2)}$ how is that relation formed?
0
votes
0answers
40 views

In this proof, why did they choose the value n/2 for the assumption? And what bearing did that have on the rest of the proof?

For the assumption step, why did they assume it holds true for n/2 specifically? And when they prove that it holds true for n, how do the steps they do there have anything to do with the n/2 ...
0
votes
2answers
43 views

How does my professor go from this exponential equation to a logarithmic one?

How does the "therefore" portion work? How does that exponential equation come to equal n(lgn + 1)?
1
vote
1answer
84 views

Find pattern in recursion

this is a example from my book Write several elements of the recursion, and see if you can find a pattern. T(n) = T(n – 1) + n T(n –1) = T(n – 2) + (n –1) T(n –2) = T(n – 3) + (n –2) T(n –3) ...
0
votes
2answers
49 views

Recursively defining a set

I have what may seem a very trivial question, but how it is answered may affect how a proof of mine is structured. It pertains to formatting and convention. When 'recursively' defining a function does ...
2
votes
1answer
125 views

how to show the convergence of an algorithm

I have two unknown variables x and y which are non linear equations to be solved. \begin{eqnarray} y=\frac {|\sin(2x+\theta)|}{\sin x\sqrt{A+2B\cos(2x+\theta)}} \nonumber \\ x=\arccos\bigg( ...
0
votes
1answer
100 views

How does one solve recurrence relations involving subproblems of different sizes?

I just studied the Master Method for solving recurrences but found out that it is applicable only to the recurrence relations having same subproblem sizes, for instance in the following recurrence : ...
0
votes
2answers
78 views

Calculating a SQRT digit-by-digit?

I need to calculate the SQRT of $x$ to $y$ decimal places. I'm dealing with $128$-bit precision, giving a limit of $28$ decimal places. Obviously, if $\,y > 28$, the Babylonian method, which I'm ...
4
votes
1answer
561 views

Fibonacci with Mortal Bunnies

I am trying to understand a twist on the Fibonacci bunnies scenario, where the bunnies die x generations after their birth (where x is a positive integer). An example is shown here. I understand the ...
2
votes
1answer
50 views

Counting permutations, with additional restrictions

There are 10 slots and some marbles: 5 red, 3 blue, 2 green, how many ways can you fit those marbles into those slots? Those marbles fit in 10!/(5! 3! 2!) ways ...
1
vote
4answers
67 views

closed form $f_n=\sqrt{2f_{n-1}}$ ? [duplicate]

I am trying to write up a proof for the convergence of this recursive function. I was wondering if there exists a closed form. Given first term in sequence is $\sqrt{2}$ and second is ...
0
votes
2answers
456 views

all possible sequences of positive integers that sum upto N and are strictly increasing

I have $N$ bricks and i have to build a staircase. A staircase will consist of steps of different sizes in decreasing order, no two step size should be same. Each step should consists of atleast one ...
1
vote
1answer
69 views

Prove $T(n) = 2T(\frac{n}{2} - 3) + n$ is $O(n\lg n)$

I just had an exam in my algorithms class and this was a question on it. I was able to craft a solution, but I'm not sure if my proof has errors. $$\begin{align} &\frac{n}{2}-3 < n & ...