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

learn more… | top users | synonyms

14
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
373 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
192 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
100 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
209 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
84 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) ...
7
votes
2answers
908 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
214 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
374 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
313 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 ...
3
votes
2answers
3k 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) \\ ...
2
votes
3answers
624 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
2answers
208 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
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
297 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
223 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 ...
4
votes
1answer
765 views

Karatsuba multiplication with integers of size 3

I understand how to apply Katarsuba multiplication in 2 digit integers. $$\begin{array} \quad & \quad & x & y \\ \times & \quad & z & w \\ \hline \quad ...
6
votes
1answer
462 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
163 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 ...
7
votes
3answers
280 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
2k 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
179 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
270 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
699 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 ...
2
votes
5answers
102 views

How to give a good guess to the recurrence relation problem

I have been trying to solve the following recurrence relation $$T(n)=2T(\frac{n}{2}) + nlgn$$ by using substitution method. I started to compute $T(1)$ ,$T(4)$,$T(8)$,$T(16)$ to guess a solution as ...
2
votes
0answers
135 views

Algorithm for reversion of power series?

Given a function $f(x)$ of the form: $$f(x) = x/(a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4+a_5x^5+...a_nx^n)$$ Let $A$ be an arbitrary (any) infinite lower triangular matrix with ones in the diagonal: $$A ...
1
vote
1answer
106 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
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
102 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
287 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
69 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
378 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
195 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
121 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 ...
2
votes
1answer
58 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
182 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
119 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
801 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
304 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
100 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
216 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
219 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
95 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
601 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
108 views

Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
0
votes
2answers
41 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
92 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 ...