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

learn more… | top users | synonyms

13
votes
6answers
1k views

How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$

How to solve this particular recurrence relation ? $$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$ such that $f_2 = 12, f_3 = 24$ and so on. I tried out a lot but due to $(-1)^n$ I am not able to ...
6
votes
2answers
328 views

unorthodox solution of a special case of the master theorem

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and ...
3
votes
3answers
150 views

Recurrence relation by substitution

I have an exercise where I need to prove by using the substitution method the following $$T(n) = 4T(n/3)+n = \Theta(n^{\log_3 4})$$ using as guess like the one below will fail, I cannot see why, ...
7
votes
3answers
1k views

Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
0
votes
3answers
93 views

How can $n \lg n = O(n^{log_3 4 - r})$?

How can I understand this bound, for me it is not true. $$n\lg n = O(n^{\log_3 4 - r})$$ where $\lg n = \log_2 n$ and $r > 0$ I'm trying to solve this recurrence $T(n) = 4T(n/3) + n\lg n$ using ...
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 ...
0
votes
2answers
79 views

Explanation needed on this rather basic recurrence solution

We are studying about recurrences in our analysis of algorithms class. As an example of the substitution method (with induction) we are given the following: $$T(n) = \lbrace 2T\left(\frac{n}{2}\right) ...
6
votes
2answers
836 views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
3
votes
1answer
195 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
5
votes
3answers
363 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
2
votes
2answers
258 views

Solving recurrences with boundary conditions

I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of. Consider this problem: Show that ...
2
votes
3answers
590 views

Prove algorithm correctness

I'm wondering if there exists any rule/scheme of proceeding with proving algorithm correctness? For example we have a function $F$ defined on the natural numbers and defined below: ...
1
vote
1answer
77 views

Does this sequence of operators in Hilbert space, given by an algorithm, terminate

Let $H$ be an infinitedimensional Hilbert space and $T$ a compact selfadjoint operator in it. Consider the following Algorithm: Let $$ H_{1}=H,\ T_{1}=T $$ and let $\lambda_{1}$ be that ...
0
votes
6answers
294 views

Obtain the formula for the following sequence

I can't seem to figure out how to find an algebraic formula for the following sequence of numbers. $$0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0$$ Can somebody ...
7
votes
1answer
217 views

Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $

I have a recurrence relation, $$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $$ for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$ I have to find the value of $a_n$ for very large values of n. I tried ...
6
votes
1answer
409 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
5
votes
1answer
158 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
1
vote
2answers
2k views

Proof by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$

How to prove by the substitution method that if $T(n) = T(n - 1) + \Theta(n)$ then $T(n)=\Theta(n^2)$? I've tried the following and got stuck $$ \begin{align} T(n) &= T(n - 1) + \Theta(n) \\ ...
7
votes
3answers
221 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
7
votes
2answers
1k views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
1
vote
2answers
3k views

Worst case analysis of MAX-HEAPIFY procedure .

From CLRS book for MAX-HEAPIFY procedure : The children's subtrees each have size at most 2n/3 - the worst case occurs when the last row of the tree is exactly half full I fail to see this ...
5
votes
1answer
168 views

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the ...
4
votes
2answers
256 views

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= ...
4
votes
1answer
683 views

Applying a Math Formula in a more elegant way (maybe a recursive call would do the trick)

This is my first post in Math section. I've been redirected here from StackOverflow, users from there suggested me to ask here. This could appear a little bit complex at first sight but afterall ...
1
vote
1answer
90 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 ...
0
votes
0answers
84 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
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 ...
5
votes
1answer
96 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 ...
4
votes
3answers
232 views

Can someone intuitively explain the towers of Hanoi and how a proof by induction can be used?

I'm having trouble understanding precisely how the proof by induction is used to show that it takes at most $2^n-1$ moves to get all the disks from one peg to another. Are there any helpful sources ...
4
votes
1answer
68 views

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
3
votes
0answers
304 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
3
votes
1answer
184 views

Nesting functions to understand nesting series

So I am working on a problem that involves an expression that has a "nested" sigma notation. Maybe "nested" isn't the correct word, because you start with an input (of your choosing) and the output ...
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 ...
2
votes
1answer
155 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
2answers
112 views

Combination/Permutation Question

I'm trying to solve a programming challenge, and I have narrowed down all the challenge to a combination/permutation problem. I ended up with 5 possible scenarios, and I need to find all possible ...
2
votes
1answer
715 views

Stepping through the Josephus problem

I'm trying to figure out how the math in the Josephus problem works exactly. I first heard of it for programming purposes so that's where my focus has been. The formula does seem to be recursive from ...
2
votes
1answer
289 views

To officially be recursion, must there be a base case?

In this Python code, the function f is defined, which then immediately calls itself: def f(): f() It's not very complicated, the first line defines the ...
2
votes
1answer
99 views

Recursion with non-equal exponents

This is my first question on this site... yesterday I asked this on cs.so but they downwote and told me that so.cs is a research-level site, not for students... I hope it's appropriate to ask this ...
1
vote
0answers
189 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 ...
1
vote
1answer
173 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
1
vote
2answers
90 views

The use of master theorem appriopriately

I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is: $$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$ Can i use the master theorem in that relation? If ...
1
vote
2answers
150 views

In mathematics, what is meant by induction?

I was going through MIT video lectures on "Introduction to Algorithms " . In order to solve recurrences by substitution the professor says that we can solve them by induction. What is actually the ...
1
vote
1answer
488 views

Worst case of Heapify is $\Omega(n \lg n)$

Worst case of Heapify is $\Omega(n \lg n)$ I know that Heapify is $\Theta(\lg n)$, but I don't know if $\Omega(n \lg n)$ is equivalent. Thanks.
0
votes
2answers
36 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
0
votes
2answers
86 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 ...
0
votes
3answers
166 views

(CHECK) $n$-bit Strings Containing a Pattern

$$\text{$\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}$}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and ...
0
votes
1answer
112 views

Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The Schröder numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The Schröder number ...
0
votes
0answers
147 views

how to solve the following recurrence $T(n) \leq 2c (\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$.

The title is pretty much self-explanatory. I don't think I have the necessary math skills to solve the recurrence. Thanks in advance. Edit: My question is how to simplify $ ... \log (\lfloor ...
-2
votes
4answers
2k views

Factorial Function - Recursive and iterative implementation

I have the function: n! = n*(n-1)*(n-2)...* 3 * 2 * 1 Which I need to sketch an implementation recursively and iteratively. Could anyone point me in the right ...