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

Groups > comp.programming > #7747

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

Show all headers | View raw

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.

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