Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: Daniel Bastos <dbastos@toledo.com>
Newsgroups: comp.programming
Subject: Re: on expressing o() in terms of O(), Omega() or Theta()
Date: Thu, 04 May 2017 08:57:40 -0300
Organization: Aioe.org NNTP Server
Lines: 71
Message-ID: <86inlgeswb.fsf@toledo.com>
References: <86var4n9nc.fsf@toledo.com>
NNTP-Posting-Host: RSvMZTbU5JGhWmBFQkv4QQ.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)
X-Notice: Filtered by postfilter v. 0.8.2
Cancel-Lock: sha1:sq8Bd1JV8w+8cfvF1CJ2XVugKbo=
Xref: csiph.com comp.programming:7747

Daniel Bastos <dbastos@toledo.com> writes:

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

I present half of a solution.  I think in order to define o() in terms
of say Theta() we need an if-and-only-if-relation.  So far I have an
if-relation.  (In Ben Bacarisse's honor, we use the notation of
subscript by juxtaposition instead of by function notation.  That is, we
write n1 instead of n(1).  Thank you!)

Theorem.  If f(n) in o(g(n)) then there is h(n) such that 

  (f(n) + h(n)) in Theta(g(n)).

Proof.  Let f(n) in o(g(n)).  This means there is an index n1 > 0
such that for any c > 0, we have

  0 <= f(n) < c g(n).  (Equation 1)

We wish to show there is h(n) such that (f + h)(n) in Theta(g(n)).
This means we need to show there are constants c1, c2 and index n2 such
that 

  0 <= c1 g(n) <= f(n) + h(n) <= c2 g(n)

for any n >= n2.

Consider h(n) = f(n).  We trivially get h(n) in o(g(n)) and consequently
there is index n3 > 0 such that for any d > 0,

  0 <= h(n) < d g(n).  (Equation 2)

Now add Equation 1 and 2 to get 

  0 <= f(n) + h(n) < (c + d) g(n),

for any n >= max(n2, n3).

This gives us the right hand side of the definition of Theta().  We need
to get the left hand side now.  We'll now apply the theorem of the
transpose symmetry[CORMEN, 3rd, page 52], namely

  f(n) = o(g(n)) if and only if g(n) = omega(f(n))

So, by the definition of omega(f(n)), we have that given e > 0, there is
an index n4 such that 

  0 <= e g(n) <= f(n)  (Equation 3)

for any n >= n4.  Adding h(n) = f(n) to Equation 3, we get 

  h(n) <= e g(n) <= e g(n) + h(n) <= f(n) + h(n),

which implies

  e g(n) <= f(n) + h(n) < (c + d) g(n),

for any n >= max(n2, n3, n4).

Now choose 

   c1 = e
   c2 = c + d
   n0 = max(n2, n3, n4)

to get

  f(n) + h(n) in Theta(g(n))

as desired.