David Hanley wrote:
>> But O(1) = O(2),
> You should do a little work in logic. You can't refute an argument
> by simply defining your answer to be correct.
In mathematics O(1) = O(2) by definition. What means O(2) to you,
precisely? One could agree that the constant in the usual
O notation enters in it, hence f = O(g) if
|f(x)| <= |g(x)| for every x (or for every x big enough? - but this
is than again not more "practical").
Mathematicians would not be too happy with it, because after some
iterations this notation probably would collapse. In fact, the main
advantage of Landau's notation is that one has not to carry around
those constants. For your (?) notation (as it stands above),
mathematicians simply write |f| <= |g| or |f(x)| <= |g(x)| for x
so and so. So, if you know the constants, a (generalized) O notation
is not necessary.
The mathematical notation is also adopted in most books about
algorithms (e.g. Cormen a.o., which I have at hand).
It is true that sometimes one can give upper bounds for complexity
with explicit constants. You are right when you say that in these
cases one should give a precise statement. If in the proof of a
theorem it is shown that |f(x)| <= 2.153 |g(x)| for every x >= 1500,
probably an author should write this also in the theorem itself.
je
In article <·················@felix.unife.it>,
Josef Eschgfaeller <···@felix.unife.it> wrote:
>David Hanley wrote:
>
>>> But O(1) = O(2),
>
>> You should do a little work in logic. You can't refute an argument
>> by simply defining your answer to be correct.
>
>In mathematics O(1) = O(2) by definition. What means O(2) to you,
>precisely?
I think that including the coefficient is intended to be useful
specifically when comparing algorithms that have the same complexity
without the coefficient. E.g. consider:
(defun my-remove (item list)
;; Make sure that we don't even share tails like REMOVE can
(remove item (copy-list list)))
If REMOVE is O(An) and COPY-LIST is O(Bn), MY-REMOVE is presumably
O((A+B)n). An O(An) algorithm always beats an O(Bn) algorithm when A<B,
but an O(An^X) algorithm eventually beats an O(Bn^Y) algorithm when X<Y,
regardless of A and B, so we usually ignore the coefficient in the latter
case.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin wrote:
> If REMOVE is O(An) and COPY-LIST is O(Bn), MY-REMOVE is presumably
> O((A+B)n). An O(An) algorithm always beats an O(Bn) algorithm when A<B,
> but an O(An^X) algorithm eventually beats an O(Bn^Y) algorithm when X<Y,
> regardless of A and B, so we usually ignore the coefficient in the latter
> case.
This kind of analysis is very useful and important, but the O()
notation, as defined by every authority I know of, has a meaning
that makes statements like "O(x)<O(1000x)" false. I don't know of
any notation that lets you state this sort of thing concisely;
if there isn't one then that explains the common use of O() for
this purpose...
--
Gareth McCaughan ················@pobox.com
sig under construction
Barry Margolin <······@bbnplanet.com> writes:
> I think that including the coefficient is intended to be useful
> specifically when comparing algorithms that have the same complexity
> without the coefficient.
Including a constant factor might be used to show something or hint at
something, but it cannot be used to proof something. It is even very
dubios when used as a informal hint.
> E.g. consider:
>
> (defun my-remove (item list)
> ;; Make sure that we don't even share tails like REMOVE can
> (remove item (copy-list list)))
>
> If REMOVE is O(An) and COPY-LIST is O(Bn), MY-REMOVE is presumably
> O((A+B)n).
I would write this as (ignoring what is being measured here):
REMOVE is A*n + O(1)
COPY-LIST is B*n + O(1)
then
MY-REMOVE is REMOVE plus COPY-LIST which is (A+B)*n + O(1)
- Marius