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

learn more… | top users | synonyms

0
votes
2answers
87 views

Recursive function into non-recursive

I have to express $a_n$ in terms of $n$. How do I convert this recursive function into a non-recursive one? Is there any methodology to follow in order to do the same with any recursively defined ...
2
votes
0answers
128 views

Subtrees of a tree

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K. for example: If ...
2
votes
3answers
141 views

What does 'i-th' mean?

I have seen a problem set for the tower of hanoi algorithm that states: Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is ...
0
votes
1answer
327 views

Master Theorem change of variables with root other than 2

I'm working on this: $$T(n) = 12T(n^{1/3}) + \log(n)^{2}$$ Using change of variables, and substituting $m = \log n$, I get as far as: $$S(m) = 12S(m/3) + m^{2}$$ I see how a square root would work ...
0
votes
1answer
192 views

Recursive Function for Pyramid-Scheme

consider a group which has 1 user. each month, every user can bring another user to join the group. the user that has been joined for 3 months, should leave the group. calculate the total membership ...
0
votes
1answer
83 views

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 theorem: ...
2
votes
1answer
96 views

Application Church-Turing thesis

I would like to give examples of problems which are solvable with an algorithm, for example the function $f$ which maps the tuple $(n,m)$ to the greatest common divisor. This map is recursive. I would ...
6
votes
2answers
191 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 ...
1
vote
1answer
130 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
46 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
121 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
100 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
280 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} ...
7
votes
1answer
95 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
66 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 ...
5
votes
2answers
192 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
61 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
168 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 ...
2
votes
2answers
122 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
0
votes
0answers
371 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
83 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
82 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
63 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
78 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
41 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
142 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
370 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
113 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 ...
1
vote
0answers
100 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
49 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
224 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
64 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
82 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
27 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
207 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
105 views

Solve recurrence formula

Thanks! That helps a lot. I think the substituting is the way to go
0
votes
1answer
146 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
89 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
122 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
96 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 ...
6
votes
2answers
324 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
55 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
712 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
278 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
150 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 ...
4
votes
2answers
254 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
vote
1answer
22 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
65 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
108 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
vote
2answers
102 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) + ...