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

learn more… | top users | synonyms

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
62 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
126 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
106 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
113 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
174 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
59 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
79 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
150 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
133 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
70 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
140 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
151 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
73 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
270 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
112 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
133 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
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
74 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
2answers
44 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
85 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
50 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
150 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
112 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
81 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
708 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
55 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
68 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
507 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
73 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 & ...
2
votes
1answer
165 views

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
2
votes
1answer
590 views

Finding Pareto optimal solution set in $O(n \log n)$ time

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says: For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a ...
0
votes
2answers
76 views

How could I describe a function whose domain is x>=1 for integers, starts at 3 f(1)=3, then multiplied by 2 f(2)=6, then by 3 f(3)=18, repeat

$$f(1)=3 \quad f(2)=6\quad f(3)=18\quad f(4)=36 \quad f(5)=108$$ How can I define this function? The function is recursive and multiplies by 2 then 3 alternatively. I know I could solve this in ...
1
vote
1answer
53 views

A long strip of paper

A strip of paper has $1024$ units in length and one unit wide, divided into 1,024 unit square. The strip is folded repeatedly. The first fold is done such that the right edge coincides with the left. ...
0
votes
1answer
51 views

Pile of $2000$ cards

A pile of cards $2000$ is labeled with integers from $1$ to $2000$, with different integers of different cards. The cards in the pile are not in numerical order. The top card is removed from the pile ...
1
vote
0answers
210 views

Recursive number digits power n sum => is there a limit of unique result numbers found?

Say you have a number xyz and you choose to split it to digits, take a power of each digit to three and summarize them. Some numbers gives same result than the original number, for example: 153 = 1^3 ...
7
votes
3answers
198 views

Error accumulation in an approximating numerical algorithm for $y_n =\int_{0}^{1} \frac{x^n}{x+10} dx $

Consider the problem of calculating the integral $$y_n =\int_{0}^{1} \dfrac{x^n}{x+10} \mathrm{d}x $$ for a positive integer $n$. Observe that $$y_n + 10y_{n-1} = \int_{0}^{1} \dfrac{x^n ...
1
vote
1answer
68 views

Convergence of Recursive algorithms

In a kind of signal processing problem I faced the following recursive (boot-strap) algorithm: $$R_{k} = R_{k-1} + (y_k-H s_{k-1})*(y_k-H s_{k-1})^T$$ $$s_k = (H^T R_k^{-1} H)^{-1} H^T R_k^{-1} ...
1
vote
1answer
56 views

Using series to produce guess for algorithm analysis

I need to find the upper asymptotic bound for the recursion: $$ T(k) = 2T(k-1)+\frac{1}{k} $$ I was able to determine: The height of this tree is $k-1$. The cost of each level is ...
1
vote
0answers
85 views

substitution method for recurrence tree

If one has recurrence function - $$T(k) = 2T(k-1)+ \frac 1k$$ how can one determine the upper and lower bounds? For upper bound, I try use 'substitution method' and drew out recurrence tree, ...
2
votes
2answers
372 views

Using Master's Theorem with $f(n) = \lg^2 (n)$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question: $$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$ I've tried to apply the Master's ...