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

Groups > comp.programming > #7592

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

Show all headers | View raw

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

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? 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).

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