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

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	Tue, 28 Mar 2017 21:10:02 -0300
Organization	Aioe.org NNTP Server
Lines	38
Message-ID	<861sthaqp1.fsf@toledo.com> (permalink)
References	<86var4n9nc.fsf@toledo.com> <20170319200229.778@kylheku.com> <86pohbn5yp.fsf@toledo.com> <20170320120639.205@kylheku.com> <86shm6j2vc.fsf@toledo.com>
NNTP-Posting-Host	PsmsIGUojJunCAfmNghHww.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:lTM/TAoqXtWRmGwKw7LPhMbFKrA=
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.programming:7672

Show key headers only | View raw

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().

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