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

learn more… | top users | synonyms

1
vote
1answer
87 views

Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$

I have a recurrence equation as follows: $$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.
1
vote
2answers
190 views

Recursive relation using successor function

What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: ...
1
vote
1answer
89 views

Recursive functions, successor function

How to show that the power function $\displaystyle A=2^{m^2}$ is primitive recursive based on successor function? Thanks much in advance!!!
3
votes
1answer
704 views

Recursive FFT java implementation

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...
0
votes
1answer
135 views

Recursive relation, how to calculate the period of repeating pattern

The qualification round of the Facebook Hacker Cup was held last weekend, and in the last problem you had to calculate the values of a vector according to this recursive relation (for some given ...
2
votes
2answers
416 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
4k 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) \\ ...
0
votes
0answers
26 views

Using the substitution method prove that T(n) = T(n - 1) + Theta(n) is Theta(n^2) [duplicate]

Possible Duplicate: I need to prove the following by using the substitution method -> $T(n) = T(n - 1) + \Theta(n)$ is $\Theta(n^2)$ The title is pretty much self explanatory. How can I ...
0
votes
3answers
160 views

Finding an approximate diagonal in a grid

Imagine a 2 dimensional grid, with a variable size of $ x*y $. For this example of figure 1, let $ x=14; y=5 $. Now one may position "pixels" in this gird. They can only be placed on the grid's points ...
0
votes
1answer
735 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
2
votes
1answer
195 views

Basic recurrence problem, not sure if solution is correct (solution included)

I have the following exercise: We know that the solution of $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \log_2 n)$. Show that the solution of this recurrence is also $\mathcal{\Omega}(n \log_2 n)$. ...
0
votes
2answers
98 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
1answer
5k views

Show that the solution to $T(n) = T(n - 1) + n$ is $O(n^2)$

Hello and thanks for taking the time to answer my question. The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I ...
0
votes
1answer
42 views

segment a line according to possibly overlapped points

There are finite number of possibly overlapped points (say 100) on a finite length line, how to partition the line into finite number of segments (say 12), each has as same number of points as ...
0
votes
3answers
116 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
3answers
265 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, ...
0
votes
2answers
338 views

How does one rewrite a recursive function to be strictly non-recursive?

Given the recursive function: $$f(0) = \frac{x^2}{2} + \frac{x}{2}, f(n) = \frac{f(n-1)}{2} + \frac{x}{2}$$ where $x$ = some integer How would one rewrite this function to be strictly ...
1
vote
5answers
650 views

How do we deal with recurrence relation characteristic equations that are not quadratic or have imaginary roots?

Suppose we have $$H(n) = H(n-1)-H(n-2) \rightarrow x^2-x+1 \rightarrow r_1 = \frac{1+\sqrt{-3}}{2}, r_2 = \frac{1-\sqrt{-3}}{2}$$ or $$H(n) = H(n-1)+H(n-2)+H(n-3) \rightarrow x^3-x^2-x-1=0$$ In ...
4
votes
3answers
409 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 ...
0
votes
2answers
70 views

Properties of algorithms

I have 2 questions. 1.Let's have an algorithm input a; x ← -7; y ← a; while x $<$ y do x ← x+5; y ← 2·x+y-6; done Question: What is the greatest "stopping" ...
1
vote
1answer
327 views

number of recursive calls

How to estimate the number of recursive calls that would be used by the code ...
2
votes
2answers
198 views

Theta bound about $\sum \lfloor {\sqrt{n}}\rfloor$

$$S_k=\sum_{n=1}^{k^2-1}\lfloor\sqrt{n}\rfloor $$ Can somebody give me an idea about the steps I should follow? Initially I thought $$n^{1/2}\log(n) \leq n^{1/2}\leq n^{3/2}$$ so $\Theta(f(n))=S_k ...
4
votes
1answer
85 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 ...
1
vote
1answer
1k views

Which approach to follow: greedy, divide-n-conquer or dynamic programming?

Given any problem say we have to pick few objects out of N so that the total weight is below W considering all objects of SAME value, A variation for this problem can be to have values assigned to ...
2
votes
2answers
138 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
2answers
644 views

How to prove that a dynamic programming algorithm is a monotonic function

I've written an algorithm, which is based on the Needleman-Wunsch algorithm for matching sequences of proteins. This algorithm is a dynamic programming approach, where the optimal matching of two ...
1
vote
4answers
91 views

Solving a simple recurrence.

This isn't a homework question, but it is a problem in my textbook. Given $T(n) = T(n-1) + n$, show that $T(n) = O(n^2)$ My approach: Given $T(n) = T(n-1)$ Need to show $T(n) = cn^2$, where $c ...
1
vote
1answer
80 views

Recursive function

For a sequence $a$, $a_1=2$, $$a_n=\frac{n-1}{a_{n-1}}+n-1$$Express $a_n$ in terms of $n$. I tried keep expanding, got many level of fraction until $n=1$, but I still can't see the pattern. ...
3
votes
0answers
259 views

Question about recursive defined functions.

This question is about counting functions. With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ...
0
votes
1answer
523 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
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 ...
4
votes
1answer
1k views

Karatsuba multiplication with integers of size 3

I understand how to apply Karatsuba multiplication in 2 digit integers. $$\begin{array} \quad & \quad & x & y \\ \times & \quad & z & w \\ \hline \quad ...
0
votes
1answer
74 views

EFA and recursive algorithm

1) Is EFA stronger than recursive algorithm? (This can be in term of proof theoretic ordinal, or whatsoever - to rephrase the question, are all problems that can be solved(and halt) by recursive ...
1
vote
2answers
158 views

implicit equation for covering a $3\times{n}$ face with $2\times{1}$ mosaics with recursion solution?

This is my university homework. I was on it for a day but I couldn't solve the problem. I found a implicitness solution for this problem: $f(2)=3$ $f(4)=11$ $f(n)=3f(n-2)+2f(n-4)$ I thought that ...
1
vote
1answer
363 views

Derive a General formula for each term of this periodic sequence?

I have a sequence $a_0 = 1, a_1, a_2, a_3, \dots$ such that $a_4 = a_{24}$ which implies that period repeats after $a_{24}$ to $a_{43}$. Each $a_n$ depends on $a_{n-1}$ only. I need general term for ...
1
vote
1answer
532 views

Sum of series with log in each term

I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i) $$ T(n) = T(n-2) + \frac{1}{lg \; n} $$ I tried few ways, like ...
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 ...
2
votes
0answers
79 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
0
votes
1answer
1k views

How to solve the recurrence $T(n)=3T(n/2)+n$

The exercise stated that i have to solve the recurrence using the Recursion-Tree Method. I have already finished the base part, which is $\Theta(n^{\lg3})$ But for the recursive part I'm having ...
2
votes
1answer
167 views

In-place inverse of DFT?

I'm trying to understand (by implementing) the Cooley Tukey algorithm for an array $[x_0, \dotsc, x_{2^N-1}]$ of real valued data. Since the input data is real valued, the spectrum will have ...
3
votes
2answers
231 views

Finding the nearest integers to real numbers defined implicitly

I was trying to bound the maximum cost of top-down merge sort: $$ f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1, $$ where $\lg n$ is the binary logarithm of $n$ and ...
2
votes
0answers
204 views

Who invented the breadth-first permutation algorithm?

My initial problem was solved here. It is about enumerating all n-tuples of a permutation in a specific order. The solution algorithm is very simple and I'm sure has been used before. However, I did ...
7
votes
1answer
234 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 ...
2
votes
0answers
79 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...
1
vote
1answer
1k views

What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
2
votes
2answers
5k 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 ...
3
votes
1answer
356 views

Karatsuba Multiplication

Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm): $$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd ...
6
votes
1answer
565 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 ...
2
votes
3answers
4k views

What will the recursion tree of Fibonacci series look like?

I am watching the Introduction to algorithm video, and the professor talks about finding a Fibonacci number in $\Theta(n)$ time at point 23.30 mins in the video. How is it $\Theta(n)$ time? Which ...
1
vote
2answers
153 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 ...