```Date: Feb 23, 2013 10:37 PM
Author: William Elliot
Subject: Re: Computationally efficient method of assessing one measure of<br> variation of a function

On Fri, 22 Feb 2013, pepstein5@gmail.com wrote:> Let N be a positive integer.  Let f be a function from the nonnegative > integers <= N to the reals.  Let d > 0.  What is a computationally > efficient way of finding the largest possible k such that there exists M > >=0, M + k <=N such that abs(f(x) - f(y)) <= d for all x, y such that x > and y are both >= M and <= M + k?What's the ranges of the variables?  Reals, integers, positive integers? > I'm also interested in continuous analogies.  For example, suppose f is > a continuous function defined on a closed interval.  How do we find the > length of the longest interval I in the domain of f such that abs(f(x) - > f(y)) <= d whenever x and y both lie in I.For continuous f:[a,b] -> R and d > 0, you want to find the largest interval I subset [a,b] with the lenght of the interval f(I) <= d?That is highly dependent upon how f varies.If f is constant, then I = [a,b].If f(x) = x, then I = [a, a+d] if a+d <= b is one maximal interval among possibly uncountable many.If b < a + d, then I = [a,b].If f(x) = rx, r > 0, then I = [a, a+d/r] if a+d/r <= b is one maximal interval among possibly uncountable many.If b < a + d/r, then I = [a,b].In general, if len f([a,b]) <= d, [a,b] is the maximum interval.It seems to me that the maximal intervals would be associatedwhere |f"| is the smallest.
```