Generalized (Divide-Et-Impera) Recurrences
These are recurrences of the form x(n) = a * x(n/b) + p(n),
where a is positive, b > 1 and p(n) is a
function whose domain is the set of positive integers,
and the value n/b is always understood as its integer part.
A typical example of this class is the recurrence satisfied by the
worst-case complexity of the merge-sort algorithm.
Exact solutions may not exist, even in the simplest cases:
therefore PURRS computes upper and lower bounds for the solution, if
the function p(n) is non negative and non decreasing.
For reasons of consistency, the initial values of these recurrences
start at 1, and are x(1), ..., x(b-1).
Please notice that in many interesting cases, PURRS gives
explicit numerical inequalities, and not just upper bounds
with hidden multiplicative factors as in the results containing the
O notation.
It is quite important to notice that the case of generalized
recurrences is much more complex than those considered above: the
reasons depend on both initial values and the fact that,
except for extremely rare cases, the solutions contain
inequalities.
We now give a detailed description of these issues, splitting the
problem of finding upper and lower bounds for the solution in two: we
first deal with the dependence on the initial conditions, and then
with the non-homogeneous part.
Dependence of the solution on the initial values
The solution always contains only one initial value, as the
reader can easily check studying the recurrence
x(n) = x(n/3).
Given our convention that the initial values are x(1) and
x(2), one can compute successively x(3) = x(1),
x(4) = x(1), x(5) = x(1), x(6) = x(2),
x(7) = x(2), x(8) = x(2),
x(9) = x(3) = x(1), ...
The precise dependence on the initial conditions has a rather ugly
shape: assume that x(n) = a * x(n/b), where a is
positive and b ≥ 2 is an integer.
Define q = q(n,b) = floor(log(n)/log(b)) where
floor(t) is the largest integer that does not
exceed the real number t, and log denotes the
natural logarithm (though, in this particular case, the base
is immaterial).
The exact solution of the given recurrence is therefore
x(n) = a^q * x( floor(n/b^q) ), where the argument of the
x function on the right belongs to the set
{ 1, 2, ..., b-1 }.
For the time being, PURRS gives an answer that, strictly speaking, is
correct only if the initial values are non negative, and it is
precisely
- a^((log(n)/log(b))*x(floor(n/b^q))/a ≤ x(n)
≤ a^((log(n)/log(b))*x(floor(n/b^q))
if a > 1;
- x(n) = x(floor(n/b^q))
if a = 1;
- a^((log(n)/log(b))*x(floor(n/b^q)) ≤ x(n)
≤ a^((log(n)/log(b))*x(floor(n/b^q))/a
if 0 < a < 1.
For those initial values that are negative, the user should exchange
upper and lower bound.
Notice that if b = 2 there is only one possible initial
value, namely x(1): PURRS knows this fact, and simplifies the
output accordingly.
Dependence of the solution on the non-homogeneous part
Since, as already remarked, a solution in closed form may not exist,
PURRS computes an upper and a lower bound for the value of
x(n) for a fairly wide class of functions p(n),
including polynomials, exponentials, logarithmic functions, the
factorial function and sums of such functions.
In these cases, the bounds computed contain explicit constants.
For the time being, PURRS does not allow parameters in the
non-homogeneous part, but in most cases the user can obtain the
solution just the same: this is best shown by means of an example.
Assume you want to solve x(n) = 2*x(n/2) + a, which PURRS
rejects as too complex.
Ask PURRS to solve x(n) = 2*x(n/2) + 1, instead, and
(assuming for simplicity that x(1) ≥ 0) you will obtain
the inequalities
-1 + 1/2*x(1)*n + 1/2*n ≤ x(n) &le -1 + x(1)*n + n
All you have to do is to multiply the part of the answer that does not
contain the initial condition by a, if a ≥ 0.
If a < 0 then you also have to exchange the two between
upper and lower bound.
In other words, the full solution of the original, parametric recurrence is:
- -a + 1/2*x(1)*n + 1/2*n*a ≤ x(n) &le -a + x(1)*n + n*a
if a ≥ 0;
- -a + 1/2*x(1)*n + n*a ≤ x(n) &le -a + x(1)*n + 1/2*n*a
if a < 0.
Future releases of PURRS will deal with these issues automatically.
Multivariate recurrences
Automatic complexity analysis frequently leads to the synthesis
of multivariate recurrence relations.
While multivariate recurrences are really hard to solve in general,
in many cases they can be converted into univariate recurrences
so that all the techniques presented above become applicable.
PURRS is often able to automatically perform such a rewriting step.
A very frequent and interesting case happens when the difference
between the arguments of the unknown function x() is constant
among all its occurrences in the multivariate recurrence relation.
For instance, this happens for any recurrence relation having the form
x(m,n) = f(x(m-1,n-1)), where the difference between
the first and second argument of x() is always m-n.
Such a recurrence can be rewritten as y(t) = f(y(t-1)),
where y(t-k) = x(m-k,n-k), for all positive integer
values of k.
Another interesting case, similar to the one above, is when the sum
of the arguments of the unknown function x() is constant.
For instance, multivariate recurrences of the form
x(m,n) = f(x(m+1,n-1)) can be rewritten as y(t) = f(y(t-1)),
where y(t-k) = x(m+k,n-k), for all positive integers k.
These rewriting techniques extend to recurrences involving more
than two variables.
Verification of the Solutions
In the case when an exact solution has been successfully found, you
can ask PURRS to check that the solution it computed actually
satisfies the recurrence you typed.
This is helpful in the fairly common case when the exact solution
PURRS found is too complex or simply too long to carry out the
computations by hand.
PURRS substitutes the suggested solution back into the original
recurrence, and checks that both sides agree as a function of the
integer variable n.
Some special tricks have been built into PURRS in order to carry out
this rather complex task as efficiently as possible.
When PURRS computes an upper or a lower bound for the solution, you
can still ask for a proof of its correctness, and PURRS will handle
the resulting inequalities.
Input/Output
- Expression may include +, -, *,
/, ^ (exponentiation), and parentheses.
All constants must be integers.
- Multiplication signs can not be omitted.
- Any single lower-case letter different from e, n
and x (e.g., a, b, c, z)
is considered as a parameter.
They can be used in the situations described above.
- The function n! can be written either as such or as
factorial(n).
In the output it always appears in the second form.
- Symbolic sums and products may be entered as
sum(symbol,initial_value,final_value,summand) or
prod(symbol,initial_value,final_value,summand)
respectively, where summand is a function of the variable
symbol.
The expression initial_value must be a non negative
integer, while final_value may depend on n.
- PURRS has some proficiency at rewriting recurrences that
are not given in its standard form: for example, if you give
2*x(n+1) as the RHS, it will solve x(n) = x(n-1)/2,
instead.
- For a positive integer k, the function
mod(n,k) is defined to give the unique non
negative integer r such that r < k and
k divides n - r. In other words,
mod(n,k) is the remainder that n
leaves when divided by k.
[Page last updated on January 18, 2013, 09:58:05.]