0

Consider this Big O relation: $f{(s,t) }= O(t^{m(s)})$, where $0 < s < 1/2$ and $m(s)< 1/2$. Since ${t_2}^{m(s)} > {t_1}^{m(s)}$, for t_2 > t_1 does this imply that one has: $f(s,{t_2}) > f(s,{t_1})$ for ${t_2} > {t_1}$? Also, is this true for any $t > 0$, for large $t$ values (how large?) or when $t$ goes to infinity?

Hass Saidane
  • 94

1 Answers1

0

Big O Notation "describes the limiting behavior of a function when the argument tends to an specific value or infinity", but do not constraint the values of that function in any way.

So if you could have a function $f(t)=\mathcal{O}(g(t))$ for $t \to \infty$ implies:

$\forall \epsilon \exists T, T<t \to |f(t)-g(t)|<\epsilon$.

But this will not imply $f$ is order preserving whatever in increasing or decreasing sense, for any range of values of $t$:

$t_1<t_2 \not\to f(t_1)<f(t_2)$ or

$t_1<t_2 \not\to f(t_1)>f(t_2)$.

You can easily build a counterexample of a function composed by piecewise segments, like a limit saw, tending to the desired limit $g(t)$, with intervals having $f(t)>g(t)$ and intervals having $f(t)<g(t)$. Hence, at every neighborhood centered on an interval intersection, the order preserving will fail.

Brethlosze
  • 3,010
  • Great answer. Thanks – Hass Saidane Nov 01 '17 at 11:31
  • So, what about the specific case above: t^m(s): where if t_2 > t_1, then t_2^m(s) > t_1^m(s) ? – Hass Saidane Nov 01 '17 at 12:27
  • $t^m$ is the limit behavior, not the requested $f(t)$ function. Without the $f(t)$ function, nothing can be said. With the $f(t)$ function, one can immediately solve the limit and check the order. – Brethlosze Nov 06 '17 at 02:37
  • What if a use a sawtooth type function as $f(t)$? Under a sawtooth, the order is not preserving at the intervals when the tooth is coming, regardless of how close the sawtooth is approaching to its limit. Hence the order will not be preserved for every $f$ and every $t$. – Brethlosze Nov 06 '17 at 21:09
  • f(t) = O(t^m) implies that there exits a constant C and a value T such that: f(t) <= Ct^m for all t >=T. Can this be used to order f(t_1) and f(t_2): if t_1 < t_2, is f(t_1^m) < f(t_2^m) since Ct_1^m < Ct_2^m, for t_1 and t_2 >T ? – Hass Saidane Nov 07 '17 at 12:13
  • No. Please consider my sawtooth function as counterexample. If $f$ is a sawtooth like, with reducing tooth amplitude for $t \to \infty$, with an asymptote equal to $t^m$, then $f$ will tend to $t^m$ and thus $f=\mathscr{O}(t^m)$. But the order will not be preserved for each saw discontinuity, hence $t_1^m \not \gt t_2^m$ and $t_1^m \not \lt t_2^m$ for infinitely many pairs $T<t_1<t_2$, for any given $T$ – Brethlosze Nov 07 '17 at 14:24
  • Agree. Let's restrict the question to a continuous function f(t). Is the ordering possible? – Hass Saidane Nov 07 '17 at 14:52
  • Change the sawtooth example by some smooth sinusoidal based signal approaching a sawtooth. The idea is still the same. The order is not related with the limit. One still would be able to find pairs in any given order. – Brethlosze Nov 10 '17 at 01:43
  • How about a smooth continuous, and infinitely differentiable function, and not sinusoidal. – Hass Saidane Nov 10 '17 at 09:13
  • IT is always possible to find a function, breaking the order. They are simply not related. – Brethlosze Nov 10 '17 at 14:06
  • Are there any conditions for breaking or not breaking the order? – Hass Saidane Nov 11 '17 at 15:08
  • No, they are only non-related properties. The condition would be to be monotonic, which is in return, is the same to be order preserving. – Brethlosze Nov 11 '17 at 16:45
  • So if f(t) is (decreasing or increasing) monotonic, the order is preserved. Is this correct? – Hass Saidane Nov 11 '17 at 17:14
  • Of course!... $f(t)$ is monotonic (increasing) equals $t_1<t_2 \to f(t_1)<f(t_2)$ . But there is nothing to prove in that case, right :)? – Brethlosze Nov 12 '17 at 05:13
  • Right. I was thinking about g(t) being monotone. – Hass Saidane Nov 12 '17 at 20:21