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

learn more… | top users | synonyms

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
257 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
329 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
634 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
390 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
309 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
135 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
632 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
257 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
504 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
72 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
151 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
350 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
513 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
78 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
164 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
228 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
198 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
231 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
77 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 ...
1
vote
2answers
4k 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
350 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
548 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
152 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
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 ...
1
vote
1answer
974 views

Ulam's problem - guessing a chosen number in a set

I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition): Suppose someone ...
2
votes
0answers
200 views

google page rank algorithm with range of values

According to the wikipedia article, the iterative google page rank algorithm is defined as follows: Can this be modified to include a range of values, not just binary, and would it look something ...
5
votes
1answer
189 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 ...
3
votes
1answer
196 views

$\mu$-recursive definition of ulam (3n+1) function

$\newcommand{\ulam}{\operatorname{ulam}}$ The ulam function is defined as $$ \ulam(x) = \begin{cases} 1 & x = 1 \\ \ulam\left( \frac{x}{2}\right) & x \text{ even}\\ \ulam(3x+1) & ...
2
votes
0answers
134 views

Help on Generating function - Analysis of Median of three - Quick Select

I am trying to find out the average case analysis of median of 3 - quick select. The recurrence relation is \begin{equation} C_{n,j} = 1 + \sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} ...
1
vote
5answers
248 views

Any fastest algorithm for $f(n) = f(n-1) \cdot f(n-2)$ where $3 \leq n \leq 1000000$

Any fastest algorithm for $$ f(n) = f(n-1)\cdot f(n-2)\quad\text{ where }\quad f(1) = 1,\quad f(2) = 2 $$ for $3 \leq n \leq 1000000 $.
5
votes
1answer
2k views

Quick sort algorithm average case complexity analysis

This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications". The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
0
votes
1answer
51 views

Algorithms and generalisation of functions

I admit I'm little bit poor in functions in mathematics. But I'm in real urge to get this riddle out. How to express $$x(n)=x(n-1)+x(n-2)+1,$$ where $n>1$ and $x(0)=0$ and $x(1)=1$, in terms of ...
1
vote
1answer
721 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
1answer
204 views

how does this reasoning for this weighted interval scheduling work?

I'm reading a dynamic programming algorithm to the weighted interval scheduling problem. There are $n$ intervals, each has a start time $s_i$, a finishing time $f_i$ and a value $v_i$. The goal is to ...
3
votes
1answer
219 views

constructive proof of the infinititude of primes

There are infinitely many prime numbers. Euclides gave a constructive proof as follows. For any set of prime numbers $\{p_1,\ldots,p_n\}$, the prime factors of $p_1\cdot \ldots \cdot p_n +1$ do not ...
1
vote
1answer
91 views

Solving this permutation

I know this is an extremely noob question, but I need some help. since I am stuck Prove the formula $$p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$$ from this answer.
0
votes
2answers
3k views

Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$

I am trying to solve the following recurrence relations using telescoping. How would I go about doing it? $T(n) = T(n-1) + 1/n$ $T(n) = T(n-1) + \log n$ thanks