Path: csiph.com!aioe.org!.POSTED!not-for-mail From: Daniel Bastos 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> 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 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.