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

Groups > comp.programming > #7588 > unrolled thread

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

Back to article view | Back to comp.programming

Contents

  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

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

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.

[toc] | [next] | [standalone]

#7589

On 2017-03-19, Daniel Bastos <dbastos@toledo.com> wrote:
> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
> any combination of them?

To warm up, first define <= and >= in terms of =.

[toc] | [prev] | [next] | [standalone]

#7591

Kaz Kylheku <336-986-7787@kylheku.com> writes:

> On 2017-03-19, Daniel Bastos <dbastos@toledo.com> wrote:
>> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
>> any combination of them?
>
> To warm up, first define <= and >= in terms of =.

I don't think that's very easy to do.  Don't think that I'm
mathematically inclined, but I happen to have a book called The
Structure of the Real Number System by Cohen and Ehrlich in which they
define an order in N in Theorem 1.13.  That's difficult work.  I don't
think I could understand that without a lot of work.

But perhaps I get your point.  The same strategy could be applied to the
original question.  That's a difficult exercise then!  Thanks for
pointing that out to me.  I had no idea until now.

Thank you.

[toc] | [prev] | [next] | [standalone]

#7592

On 2017-03-20, Daniel Bastos <dbastos@toledo.com> wrote:
> Kaz Kylheku <336-986-7787@kylheku.com> writes:
>
>> On 2017-03-19, Daniel Bastos <dbastos@toledo.com> wrote:
>>> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
>>> any combination of them?
>>
>> To warm up, first define <= and >= in terms of =.
>
> I don't think that's very easy to do.

That depends. We can define 'x = a' in terms of 'x <= a' and 'x >= a'
very easily like this:

  x = a    <==iff===>   x <= a and x >= a

This reasoning over to the big Oh family which are defined using
inequalities. Suppose we use the Knuth definition of Omega, which
is the inverse of big Oh:

  f is O(g)  <==>   g is Omega(f)

If both are true, then, I think: f is Theta(g):

  f = Theta(g)   iff   f = O(g) and g = Omega(f)

If f grows no faster than g, but also at least as fast as g, then it
grows exactly as fast as g!  What's left is to show that using the
expanded definition of what these notations mean: the quantified
expressions over inequalities.  The definition of Theta involves the
binding of two constants under existential quantifiers, and asserting
that one function is sandwiched between these two constant factors of
the other, for sufficiently large values of the independent variable.

Now about o in terms of Theta and the others: which little o definition
are you using? The problem is that the definitions of big and little O
are very similar. There is a hair-splitting difference which shows up as
in one logical quantifier being universal in little Oh whereas it is
existential in big Oh.  f = o(g) asserts that there is a sufficiently
large value of the independent variable x such that for all positive
constants C,  |f(x)| <= C|g(x)|.  Whereas big O only asserts that this
is true for some sufficiently large, positive constant C, not for all
positive constants C.

Basically, you have to work with the expanded versions of these
definitions and see if or how you can work one in terms of the others.

Is there some logical combination of several of them which will
derive the one you want (using whatever manipulation is necessary:
reshuffling the quantifiers, etc).

[toc] | [prev] | [next] | [standalone]

#7594

Kaz Kylheku <336-986-7787@kylheku.com> writes:

> On 2017-03-20, Daniel Bastos <dbastos@toledo.com> wrote:
>> Kaz Kylheku <336-986-7787@kylheku.com> writes:
>>
>>> On 2017-03-19, Daniel Bastos <dbastos@toledo.com> wrote:
>>>> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
>>>> any combination of them?
>>>
>>> To warm up, first define <= and >= in terms of =.
>>
>> I don't think that's very easy to do.
>
> That depends. We can define 'x = a' in terms of 'x <= a' and 'x >= a'
> very easily like this:
>
>   x = a    <==iff===>   x <= a and x >= a

Sure.  That's different from defining <= and >= in terms of =.

> This reasoning over to the big Oh family which are defined using
> inequalities. Suppose we use the Knuth definition of Omega, which
> is the inverse of big Oh:
>
>   f is O(g)  <==>   g is Omega(f)
>
> If both are true, then, I think: f is Theta(g):
>
>   f = Theta(g)   iff   f = O(g) and g = Omega(f)
>
> If f grows no faster than g, but also at least as fast as g, then it
> grows exactly as fast as g!  What's left is to show that using the
> expanded definition of what these notations mean: the quantified
> expressions over inequalities.  The definition of Theta involves the
> binding of two constants under existential quantifiers, and asserting
> that one function is sandwiched between these two constant factors of
> the other, for sufficiently large values of the independent variable.
>
> Now about o in terms of Theta and the others: which little o definition
> are you using? 

I think the same as yours. 

Def.  We say f in o(g) if there exists a natural number n(0) > 0 such
that 

     0 <= f < c g

for any n >= n(0) and for all c > 0, c being a real number.

> The problem is that the definitions of big and little O are very
> similar. There is a hair-splitting difference which shows up as in one
> logical quantifier being universal in little Oh whereas it is
> existential in big Oh.  f = o(g) asserts that there is a sufficiently
> large value of the independent variable x such that for all positive
> constants C, |f(x)| <= C|g(x)|.  Whereas big O only asserts that this
> is true for some sufficiently large, positive constant C, not for all
> positive constants C.
>
> Basically, you have to work with the expanded versions of these
> definitions and see if or how you can work one in terms of the others.
>
> Is there some logical combination of several of them which will
> derive the one you want (using whatever manipulation is necessary:
> reshuffling the quantifiers, etc).

I do have reshuffling the quantifiers in mind.  I know 4 theorems about
reshuffling quantifiers.

1. For any x, P(x) iff not exists x such that ~P(x).
2. Exists x, P(x) iff not for all x such that ~P(x).
3. For any x, ~P(x) iff not exists x such that P(x).
4. Exists x, ~P(x) iff not for any x such that P(x).

(Using both ~ and ``not'' as negation to ease reading and writing.)

Looking at my definition of o(), I could rewrite it as:

     for any c > 0  (for any n > n(0), P(c,f,g))

which is equivalent to 

     there is no c such that ~(for any n > n(0), P(c,f,g))

which is equivalent to 

     there is no c such that some n > n(0) satifies ~P(c,f,g).

Expanding ~P(), we get 

     ~P(c,f,g) iff 0 > f >= c g.

Therefore the definition of o() says that no suitable c exists such that
some index n > n(0) satisfies c g <= f < 0.  (Equation 1.)

That's obviously true as c, g and f are all positive constant and
functions, respectively.  Nevertheless, the point of my investigation is
to see if I can somehow introduce Omega(), O() or Theta() in places of
these statements.

The definition of Omega() uses ``c g <= f'', hence perhaps I can write

  f in o(g) iff no c exists such that f in Omega(g) for some n > n(0).

I'm worried about the ``< 0'' in Equation 1.  I'm very confused at this
point.  I don't know if what I just did is correct and whether it takes
anywhere interesting.  (I did mange to introduce Omega, though.  That
illuminates things a bit.)  Thank you.

[toc] | [prev] | [next] | [standalone]

#7672

Daniel Bastos <dbastos@toledo.com> writes:

> Kaz Kylheku <336-986-7787@kylheku.com> writes:
>
>> On 2017-03-20, Daniel Bastos <dbastos@toledo.com> wrote:
>>> Kaz Kylheku <336-986-7787@kylheku.com> writes:
>>>
>>>> On 2017-03-19, Daniel Bastos <dbastos@toledo.com> wrote:
>>>>> Is it possible to *define* o() in terms of O(), Omega() or Theta() --- or
>>>>> any combination of them?
>>>>
>>>> To warm up, first define <= and >= in terms of =.
>>>
>>> I don't think that's very easy to do.
>>
>> That depends. We can define 'x = a' in terms of 'x <= a' and 'x >= a'
>> very easily like this:
>>
>>   x = a    <==iff===>   x <= a and x >= a
>
> Sure.  That's different from defining <= and >= in terms of =.

I think I might have catched the spirit.  You're saying o() is like the
operator < while O() is like <= and Theta() is like =.  

Considering only natural numbers, if n < m, then there is a natural d
such that 

     n + d = m.

Using the same idea for functions f(n) and g(n), we may state the
following claim.

Claim.  f(n) in o(g(n)) if and only if there is h(n) such that

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

If I can prove this, then I can define o() in terms of Theta().

[toc] | [prev] | [next] | [standalone]

#7673

Daniel Bastos <dbastos@toledo.com> writes:

> I think I might have catched the spirit.

Caught. :-)

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web