Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
12
votes
6answers
600 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 ...
8
votes
3answers
432 views
Karatsuba vs. Schönhage-Strassen for multiplication of polynomials
I am wondering how to most effectively multiply two polynomials with several 100's of coefficients, each coefficient having 1000-2000 decimal digits.
I know Schönhage-Strassen begins to outperform ...
7
votes
1answer
179 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
2answers
82 views
Has anything useful come from Ackermann's Function?
Here is the function:
if (m == 0)
return n + 1;
else if (n == 0)
return A(m-1, 1);
else
return A(m-1, A(m, n-1));
This seems like an interesting ...
6
votes
1answer
40 views
Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$
I'm trying to solve the following recurrence :
$$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$
I've tried substituting $n$ for some other variables to transform the above to something easier without ...
5
votes
3answers
443 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 ...
5
votes
3answers
804 views
Using Horner's Method
I'm trying to evaluate a polynomial recursively using Horner's method.
It's rather simple when I have every value of $x$ (like: $x+x^2+x^3...$), but what if I'm missing some of those? Example: ...
5
votes
2answers
180 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)= ...
5
votes
1answer
131 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 ...
5
votes
2answers
623 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 ...
5
votes
2answers
754 views
Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$
I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
4
votes
3answers
2k views
Worst case complexity of the quicksort algorithm
Good evening,
I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
4
votes
1answer
245 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 ...
4
votes
3answers
68 views
Need help about solving a recurrence relation
I have a recurrence relation which is like the following:
$$
T(n) = 2T(n/2) + \log_2 n.
$$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$$
...
4
votes
2answers
243 views
Numerical method for finding the square-root.
I found a picture of Evan O'Dorney's winning project that gained him the first place in the Intel Science talent search. He proposed a numerical methods to find the square root, that gained him ...
4
votes
1answer
196 views
Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?
This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi.
Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
4
votes
1answer
171 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 ...
4
votes
1answer
669 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 ...
4
votes
2answers
171 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 ...
4
votes
0answers
119 views
Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?
For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $ \small z^2 $ by ...
3
votes
4answers
826 views
Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed
Update:
This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.
http://www.youtube.com/watch?v=VbSwwos4R2E
Hi, I ...
3
votes
1answer
192 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 ...
3
votes
1answer
137 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 ...
3
votes
3answers
839 views
What is the bound of : $ T(n)=T(n-2)+\log(n)$?
Given : $T(n)=T(n-2)+\log(n)$
I need to find the bound for the above recurrence .
So:
$$\begin{align*}
T(n-2)&=T(n-2-2)+\log(n-2)\\
&=T(n-4)+\log(n-2)\\
T(n)&=T(n-2)+\log(n)\\
...
3
votes
2answers
143 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 ...
3
votes
2answers
139 views
Can this be solved by induction? (number of ways of cutting a rod into pieces)
I am reading an algorithm example.
The example is about Rod cutting.
The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...
3
votes
1answer
558 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 ...
3
votes
1answer
128 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) & ...
3
votes
2answers
190 views
Determining a recurrence relation (Homework)
Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T.
The nucleotides are ...
3
votes
1answer
114 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 ...
3
votes
2answers
97 views
3
votes
1answer
57 views
Give a combinatorial proof of the recurrence relation
Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation
$$F_n = \sum_{i=1} ...
3
votes
1answer
261 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 ...
3
votes
1answer
37 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
130 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 ...
3
votes
0answers
142 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
2answers
85 views
recursive relation with sequences
I am not sure how to properly do this question but I am told that the solution I came up with is wrong and I dont see how...I basically used algebra and plugging of variables and rearranging ...
3
votes
0answers
96 views
Recursion closed form [closed]
Is there a theorem stating that all recursive problems cannot have a closed form? Or the other way around, stating that all recursive problems can have a closed form.
2
votes
3answers
82 views
how many times will a function print to the console?
I have the following snippet:
public Foo(int n)
{
for (int i=0; i<n; i++)
{
new Foo(i)
}
console.writeln("?")
}
For a given $n$, how ...
2
votes
2answers
315 views
Analysis of algorithms and recurrence relations
Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p$ a polynomial of degree $n$, the corresponding ...
2
votes
3answers
475 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:
...
2
votes
3answers
84 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 ...
2
votes
2answers
95 views
How to define divisibility recursively?
Let $d(x,y)=1$ if $x$ is divisible by $y$, and $=0$ otherwise.
How can I define $d(x,y)$ in terms of just the basic primitive recursive functions (zero, successor, identity, projection) and the ...
2
votes
2answers
70 views
Recurrence Relation for Strassen
I'm trying to solve the following recurrence relation (Strassen's):-
$$
T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\
1 & \text{if } n \leq 2
\end{cases}
...
2
votes
2answers
113 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
2answers
100 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 ...
2
votes
2answers
76 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
197 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
3answers
1k views
Recurrence equation $T(n)=3T(\sqrt{n}) +1$
I need to find an exact solution to the following recurrence using substitution (change of variables).
$$
T(n) = 3T(\sqrt{n}) + 1, \quad \text{ when } n > 2,
$$
and $$ T(2) = 1 .$$ I can't get ...
2
votes
1answer
69 views
How to prove that all the $a_i$ will be the same after inf operations?
Given some real number :$$a_1,a_2,...,a_n$$Every time I chose two of them $a_i$ and $a_j$ and set both of them to $\frac{a_i+a_j}{2}$.
Now I have operated $T$ times,when $T$ is infinite,I guess that ...
