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

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