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

Groups > alt.algebra.help > #4869

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

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 alt.algebra.help | Previous | Next | 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

csiph-web