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

Groups > comp.programming > #7672

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

Show all headers | 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().

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