Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #7594

Re: on expressing o() in terms of O(), Omega() or Theta()

Show all headers | View raw

Kaz Kylheku <336-986-7787@kylheku.com> writes:

> On 2017-03-20, Daniel Bastos <dbastos@toledo.com> wrote:
>> Kaz Kylheku <336-986-7787@kylheku.com> writes:
>>
>>> On 2017-03-19, Daniel Bastos <dbastos@toledo.com> wrote:
>>>> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
>>>> any combination of them?
>>>
>>> To warm up, first define <= and >= in terms of =.
>>
>> I don't think that's very easy to do.
>
> That depends. We can define 'x = a' in terms of 'x <= a' and 'x >= a'
> very easily like this:
>
>   x = a    <==iff===>   x <= a and x >= a

Sure.  That's different from defining <= and >= in terms of =.

> This reasoning over to the big Oh family which are defined using
> inequalities. Suppose we use the Knuth definition of Omega, which
> is the inverse of big Oh:
>
>   f is O(g)  <==>   g is Omega(f)
>
> If both are true, then, I think: f is Theta(g):
>
>   f = Theta(g)   iff   f = O(g) and g = Omega(f)
>
> If f grows no faster than g, but also at least as fast as g, then it
> grows exactly as fast as g!  What's left is to show that using the
> expanded definition of what these notations mean: the quantified
> expressions over inequalities.  The definition of Theta involves the
> binding of two constants under existential quantifiers, and asserting
> that one function is sandwiched between these two constant factors of
> the other, for sufficiently large values of the independent variable.
>
> Now about o in terms of Theta and the others: which little o definition
> are you using? 

I think the same as yours. 

Def.  We say f in o(g) if there exists a natural number n(0) > 0 such
that 

     0 <= f < c g

for any n >= n(0) and for all c > 0, c being a real number.

> The problem is that the definitions of big and little O are very
> similar. There is a hair-splitting difference which shows up as in one
> logical quantifier being universal in little Oh whereas it is
> existential in big Oh.  f = o(g) asserts that there is a sufficiently
> large value of the independent variable x such that for all positive
> constants C, |f(x)| <= C|g(x)|.  Whereas big O only asserts that this
> is true for some sufficiently large, positive constant C, not for all
> positive constants C.
>
> Basically, you have to work with the expanded versions of these
> definitions and see if or how you can work one in terms of the others.
>
> Is there some logical combination of several of them which will
> derive the one you want (using whatever manipulation is necessary:
> reshuffling the quantifiers, etc).

I do have reshuffling the quantifiers in mind.  I know 4 theorems about
reshuffling quantifiers.

1. For any x, P(x) iff not exists x such that ~P(x).
2. Exists x, P(x) iff not for all x such that ~P(x).
3. For any x, ~P(x) iff not exists x such that P(x).
4. Exists x, ~P(x) iff not for any x such that P(x).

(Using both ~ and ``not'' as negation to ease reading and writing.)

Looking at my definition of o(), I could rewrite it as:

     for any c > 0  (for any n > n(0), P(c,f,g))

which is equivalent to 

     there is no c such that ~(for any n > n(0), P(c,f,g))

which is equivalent to 

     there is no c such that some n > n(0) satifies ~P(c,f,g).

Expanding ~P(), we get 

     ~P(c,f,g) iff 0 > f >= c g.

Therefore the definition of o() says that no suitable c exists such that
some index n > n(0) satisfies c g <= f < 0.  (Equation 1.)

That's obviously true as c, g and f are all positive constant and
functions, respectively.  Nevertheless, the point of my investigation is
to see if I can somehow introduce Omega(), O() or Theta() in places of
these statements.

The definition of Omega() uses ``c g <= f'', hence perhaps I can write

  f in o(g) iff no c exists such that f in Omega(g) for some n > n(0).

I'm worried about the ``< 0'' in Equation 1.  I'm very confused at this
point.  I don't know if what I just did is correct and whether it takes
anywhere interesting.  (I did mange to introduce Omega, though.  That
illuminates things a bit.)  Thank you.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on expressing o() in terms of O(), Omega() or Theta() Daniel Bastos <dbastos@toledo.com> - 2017-03-19 20:12 -0300
  Re: on expressing o() in terms of O(), Omega() or Theta() Kaz Kylheku <336-986-7787@kylheku.com> - 2017-03-20 03:13 +0000
    Re: on expressing o() in terms of O(), Omega() or Theta() Daniel Bastos <dbastos@toledo.com> - 2017-03-20 15:44 -0300
      Re: on expressing o() in terms of O(), Omega() or Theta() Kaz Kylheku <336-986-7787@kylheku.com> - 2017-03-20 19:33 +0000
        Re: on expressing o() in terms of O(), Omega() or Theta() Daniel Bastos <dbastos@toledo.com> - 2017-03-21 08:17 -0300
          Re: on expressing o() in terms of O(), Omega() or Theta() Daniel Bastos <dbastos@toledo.com> - 2017-03-28 21:10 -0300
            Re: on expressing o() in terms of O(), Omega() or Theta() Daniel Bastos <dbastos@toledo.com> - 2017-03-29 09:22 -0300
  Re: on expressing o() in terms of O(), Omega() or Theta() Daniel Bastos <dbastos@toledo.com> - 2017-05-04 08:57 -0300

csiph-web