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

From	Daniel Bastos <dbastos@toledo.com>
Newsgroups	comp.programming, alt.algebra.help
Subject	on expressing o() in terms of O(), Omega() or Theta()
Followup-To	comp.programming
Date	2017-03-19 20:12 -0300
Organization	Aioe.org NNTP Server
Message-ID	<86var4n9nc.fsf@toledo.com> (permalink)

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show all headers | View raw

Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
any combination of them?

I know I can express o() in terms of omega(): f in o(g) iff g in
omega(f).  (CORMEN, page 52, 3rd edition.)

I can draw some easy relationships, but I haven't found an iff-relation
so as to define o().

Fact.  If f in o(g) then g in Omega(f).

Proof.  Suppose f in o(g).  Then there's n(0) such that

  0 <= f(n) < c g(n)

for any c > 0 and for any n >= n(0).  Fix c so that

  0 <= 1/c f(n) < g(n)

for any n >= n(0).  Therefore g in Omega(f). QED.

I don't think the converse is true, but I can't prove it.  If I'm right,
then o() cannot be defined in terms of Omega() alone.  Perhaps it could
be defined using a combination of O(), Omega and Theta().  Any ideas?

Thank you.

Back to comp.programming | Previous | Next — 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