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

Path	csiph.com!aioe.org!.POSTED!not-for-mail
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	Sun, 19 Mar 2017 20:12:39 -0300
Organization	Aioe.org NNTP Server
Lines	26
Message-ID	<86var4n9nc.fsf@toledo.com> (permalink)
NNTP-Posting-Host	BuEqJTf8bEmpZhBIUMG+Zw.user.gioia.aioe.org
Mime-Version	1.0
Content-Type	text/plain
X-Complaints-To	abuse@aioe.org
User-Agent	Gnus/5.13 (Gnus v5.13) Emacs/24.3 (windows-nt)
Cancel-Lock	sha1:pIhuatpfmgSrqperMvBAau/63cM=
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.programming:7588 alt.algebra.help:4869

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show key headers only | 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