Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.
1
vote
1answer
41 views
Register Machine on Fibonacci Numbers
This problem is easy to understand but I am struggling to come up with any solutions.
According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
0
votes
0answers
35 views
Finding the value of an algebric expression
I have this expression $Ax+By+Cz$ where $x,y,z \geq 0$ and are integers. Suppose I am given a value $T$; I want to find the largest value which is less than $T$ and which cannot be generated by ...
0
votes
1answer
19 views
Recursive Definitions with Converse
I think I know how to solve i. and ii., but not iii:
Base Case: $(0,0) \in S$
Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$.
(For i and ii): Prove that if $(a,b) \in ...
1
vote
3answers
60 views
HOW TO: Recurrence Relation $T(n) = 2T(n^\frac{1}{2}) + c$
I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$?
I've ...
2
votes
2answers
67 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}
...
1
vote
2answers
27 views
Tight asymptotic upper bounds on specific recurrences
give a tight asymptotic upper bound (() notation) on the solution to each of the following recurrences.
$T(n)=2T(n/8) + \sqrt[3]n$
$T(n)=T(n/3) + T(n/4) + 5n$
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 ...
1
vote
1answer
20 views
Solving recurrenc using recurrence tree method.
I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$.
I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
2
votes
0answers
13 views
Repertoire method for solving recursions
I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics:
$g(1) = \alpha;$
$g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1
I have assumed the closed form to ...
0
votes
2answers
37 views
Equation of a curve whose difference in ordinate values form an arithmetic sequence
I have the following recurrence equation that I have obtained while trying to solve a problem:-
$$T(0) = 1$$
$$T(n) = T(n-1) + 9n - 8: n \ge 1$$
The values of $T(n)$ for $n = 0,1,2,... $ are as ...
1
vote
1answer
46 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
...
0
votes
0answers
56 views
How to find integer solutions of an equation using approximation methods?
If I have a function called $f(x)$ that have several roots, integers and not integers. How can I find just the integer ones by approximations methods?
A simple example would be ...
2
votes
1answer
36 views
Quadratic Forms and Newton's Method
Consider the function $f(x,y) = 5x^2 + 5y^2 -xy -11x +11y +11$. Consider applying Newton's Method for minimizing $f$. How many iterations are needed to reach the global minimum point? Why should ...
1
vote
1answer
47 views
How do I determine if two of my software's representation of algebraic numbers are equal?
I have software which stores information about algebraic numbers with absolute precision. If you build it up by creating instances of a Python representation of an integer, float, Decimal, or string, ...
1
vote
0answers
52 views
How to deduce the results of response time by this trajectory approach?
First, we denote this:
And
And we get this right property( $last_i$ means the last node on $τ_i$):
And:
$Smin_i^h$ = $\sum_{h'=first_i}^{h-1} ({C_i^{h'} + L_{max})}$
$Smax_i^h$ = ...
2
votes
3answers
44 views
Divide et impera recurrence, why induction does not work?
$$
T(n) = T\left(\frac n2\right) + 2^n
$$
where $n \ge 1$ and $T(1) = 1$. If I understand the substitution method and the induction, I can guess that $T(n) = O(2^n)$.
I must prove that $T(n) = ...
0
votes
1answer
37 views
Identify Type of Recursive Sequence?
I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
0
votes
0answers
19 views
When do floors ceilings matter in recursions and when can we just omit then?
The title is pretty much self explanatory.. When solving recurrences in our Algorithm Analysis class sometimes, we omit the floors and ceilings and sometimes we dont. Can you please explain what's the ...
0
votes
0answers
18 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
2answers
58 views
Convergence of a Recursive Sequence - An Example
Consider the sequence
$\displaystyle x(k+1) = \frac{1}{2}\left(x(k) + \frac{a}{x(k)}\right)$
where $x(k)$ stands for the $k$th term of the sequence. What does this process converge to, and what is ...
2
votes
0answers
42 views
Recursive Sequence from Finite Sequences
I'm searching for the name of these kind of sequences:
Suppose you start off with a finite sequence containing one term:
S0 = {3}
To get the next sequence you ...
0
votes
0answers
44 views
Prove correctness of the algorithim
Consider the following algorithm min which takes lists x,y as parameters and returns the zth smallest element in union of x and y.
Pre conditions: X and Y are sorted lists of ints in increasing order ...
1
vote
0answers
42 views
Non overlapping areas algorithm
One of my fellow members on stackoverflow has posted a question thread which concerns how to write a mathematical equation to calculate the exposed areas of a window from a group of windows (like on ...
1
vote
1answer
39 views
Balancing two sets while items in one are unmovable
I'm working on a following problem: Given two sets containing jars, each of which is assigned a random weight (weight is a real number), find a way to balance two sets by weight, i.e. the difference ...
0
votes
4answers
118 views
Solving recurrence relations (change variable etc.) problems
I have been given
$$f(1) = 3\\
f(2) = 8\\
f(n) = 6f(n/2) - 8 f(n/4) \;,\;\; n > 0$$
How would I go about solving this? I've tried working so hard to get this to no avail. If someone can ...
1
vote
0answers
38 views
Solving Recursive Equations: How to transform the domain in such cases?
I understand that a widely-used recursive equation for the Binary Search is as follows:
$$
\begin{align}
T(1) &= 1\\
T(n) &= T(\tfrac{n}{2}) + 1, \quad n>1
\end{align}
$$
In order to solve ...
0
votes
1answer
38 views
Bounded recursive sequence
I would like to know if there are known bounded recursive sequence (non monotonic):
It shouldn't be a constant, neither a convergent sequence, nor a periodic one.
(I am not asking for a true random ...
1
vote
0answers
19 views
Algorithm for approaching zero delta.
I'm working on translating an old program for a gas-mixing furnace, and I have a logic problem that I believe I need help on the math with.
I have the specimen temperature ($T$), a variable called ...
1
vote
1answer
48 views
Dynamic Programming— Variable Width Bin (Equi-Depth) Histogram
Given some data, and a fixed number of bins (k)-- How can I design a Dynamic Programming algorithm that minimizes the largest difference between bin sizes?
In other words, with a set number of bins ...
3
votes
2answers
96 views
0
votes
1answer
72 views
Solving the following recurrence relation
I have a recurrence relation, it is like the following:
$$
T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm}
$$
To solve this and find a Θ bound, i tried the following: I ...
1
vote
2answers
52 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 ...
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:
$$
...
2
votes
0answers
83 views
Is there a closed form for this recurrence?
Given
$$
E_{n,k} =
\begin{cases}
0 & \text{ if } n \leq k \\
n & \text{ if } k = 0 \\
\sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise }
\end{cases}
$$
I wonder is there ...
4
votes
2answers
167 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 ...
0
votes
1answer
34 views
Identifying a pattern in an array
Is there a way to identifying a pattern and/or recursive function for an array?
If yes, how can I do this. Could anyone please help me with some information and/or resource for this?
Any help is ...
1
vote
2answers
164 views
Solving a recurrence relation using master method
I know that the Master theorem is used for the recurrence relations of the form:
$$T(n) = aT(n/b) + f(n)$$
In my question, I am supposed to solve the following recurrence relation by using Master ...
2
votes
1answer
131 views
recurrence-relation via master theorem
This is homework assignment on proving algorithm time complexity using Master Theorem. I have been trying to solve it for several hours by now with no luck. Can someone please at least explain, what ...
0
votes
1answer
116 views
Solving $T(n)=4T(\frac{n}{2})+n^2$
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 ...
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)= ...
-1
votes
2answers
119 views
Show that the solution to $T(n) = (n - 1) + 1$ is $O(n^2)$ [closed]
The title pretty much says it all.. Don't know where to start solving this recurrence.. I need to solve this by substitution method. Thanks a lot
0
votes
0answers
87 views
Using Secant Method to find number of roots
I have a discrete function,
$ y=F(N) $
where $N$ is positive integer, and I don't know number of roots of this function.
Can I use Secant Method to find number of roots?
For example, If this function ...
1
vote
1answer
19 views
Square terrain recurrence derivation
You have a square terrain with area $A > 0$. You want to add information into the terrain. You want to subdivide the terrain into $4$ quadrants, process them individually, and assemble the results. ...
1
vote
0answers
29 views
Confusion related to time complexity of fast Fourier transform
I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.
It says that lets say I have a polynomial of ...
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} ...
-1
votes
0answers
32 views
Regenerate numeric series [duplicate]
I am searching for a mathematical technique by which I can perform the following.
Let me explain first what I want to do.
Consider a numeric series:
$23, 45, 42, 56, 12, 56 \ldots$
Now, I want ...
1
vote
2answers
38 views
Θ(n) + O(n) = ? (recurrence equation)
If I have a recurrence equation like:
T(n) <= T(n/2) + Θ(n) + O(n)
Is the above expression equal to:
T(n) <= T(n/2) + Θ(n)
Or is that expression equal to:
T(n) <= T(n/2) + ...
0
votes
1answer
204 views
solving recurrence relation by substitution method and find asymptotic bound
Solve the following recurrence relations and give a bound for each of them.
$T(n)= 2T(n-3)+1$
$T(n) = 5T(n-4)+n$
0
votes
2answers
169 views
Solving Recurrence T(n) = T(n − 3) + 1/2;
I have to solve the following recurrence.
$$\begin{gather}
T(n) = T(n − 3) + 1/2\\
T(0) = T(1) = T(2) = 1.
\end{gather}$$
I tried solving it using the forward iteration.
$$\begin{align}
T(3) ...
0
votes
0answers
44 views
Solving the recurrences of algorithms
Im having some trouble understanding recurrences.
I have an assignment where I have to solve some recurrences, theyre generally in the form of:
$$T(n) = aT(n/b) + f(n)$$
I have 3 general formulas ...
