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

learn more… | top users | synonyms

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
78 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
193 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
102 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
81 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
122 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
98 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
76 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
507 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
49 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
422 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 & ...
2
votes
1answer
156 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
524 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
74 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
190 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
162 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
65 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
77 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
326 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 ...
0
votes
0answers
77 views

Vector based update for recursive least squares

I understand that to solve a recursive least squares problem one can update whole system of equation with or without growing memory when new sample or data added to the data vector. But my question ...
2
votes
2answers
61 views

Do all recursive fuctions also have a non-recursive version of itself?

Is there any proof that states that any recursive function has to have a non-recursive function that has the same output as the recursive function?
3
votes
1answer
194 views

Computing sums of divisors in $O(\sqrt n)$ time?

I have a sequence: $1,3,5,8,10,14,16,20,23,27,\dots$ I know that the recursive relation is: $$p[i] := p[i-1] + \text{number of factors of $i$}, \quad \text{with $p[1]=1$.}$$ How do I solve this ...
1
vote
1answer
230 views

Sorting Numbers into Groups

I have a list of numbers N1,N2,N3………… The list must be grouped into groups of 3 G1,G2,G3….. The sum of Each Group must be >= X, The sum of Each Group must be <= Y I understand that there may be ...
2
votes
1answer
97 views

Show the following matrix recursion is symmetric

I need to show the following matrix equation is symmetric and I'm not sure where to start: $A_i=\sum_{j_1=1}^{i-2}2(i-j_1-1){i-2 \choose j_1-1}A_{j_1}\Big(\sum_{j_2=1}^{i-j_1-1}{i-j_1-2 \choose ...
0
votes
1answer
86 views

Recursive fibonacci algorithm correctnes? [proof by induction]

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction. here is my recursive version of ...
3
votes
2answers
81 views

Filling the plane with a sequence

I am not sure if this is the right stack to ask this question, but since there is a definite fractal dimension to it, I thought I'd give it a go. The problem I am facing is one of calculating an ...
0
votes
1answer
123 views

Solving recursive relations using matrix method.

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in ...
4
votes
1answer
47 views

After $n$ iterations of the continued fraction algorithm, what kind of rational numbers will have terminated?

For a positive real number $r_0$, we have the continued fraction recursive algorithm: \begin{align} &r_n\in\mathbb{Z}\implies\text{terminate the algorithm}\\ &\text{else } r_{n+1} = ...
0
votes
0answers
92 views

uncleared Josephus problem equation?

I have been going through this problem and came across the simple solution as shown in Wikipedia. The formula for this solution is $$f(n,k)=((f(n-1,k)+k-1) \bmod n)+1$$ $$f(1,k)=1.$$ But due to ...
0
votes
1answer
243 views

Recursive formula for subset sum?

Wikipedia describes an algorithm for the subset sum problem which runs in time $O(2^{\frac{n}{2}})$. It works by dividing the set in half once, computing all the sums in each half (cleverly ...
2
votes
1answer
95 views

Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
0
votes
0answers
138 views

Bluestein Algorithm for Fast Fourier Transform

Can anyone demonstrate the full algorithm of Fast Fourier Transform? Because from Wikipeida and other internet sources, I saw that there are different ways of padding. So can anyone tell me when the ...
1
vote
1answer
149 views

On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$. Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$ We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in ...
0
votes
4answers
572 views

Second-Order, Linear Inhomogeneous Recurrence Relation With Constant Coefficients

How does one solve the general recurrence relation $$s_n=\alpha s_{n-1}+\beta s_{n-2}+\zeta(n)?$$
2
votes
2answers
110 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...