Barry Margolin wrote:
>> In mathematics O(1) = O(2) by definition. What means O(2) ... ?
> I think that including the coefficient is intended to be useful
> specifically when comparing algorithms that have the same complexity
> without the coefficient.
A mathematically correct notation for such simultaneous comparisons
would be using vectors of functions, and perhaps to write
(f(n), g(n), h(n)) = O(n, 2n, 5 n log n)
this meaning that there exist constants A and m such that
|f(n)| <= A n, |g(n)| <= 2 A n, |h(n)| <= 5 A n log n.
for all n >= m. Also this notation is a little dangereous, because
one could doubt whether it doesn't mean
|f(n)|^2 + |g(n)|^2 + |h(n)|^2 <= A (n^2 + 4 n^2 + 25 n^2 (log n)^2)
for example.
If one wants to do it in natural language, one could write less
formally something like
----------------------------------------------------
f(n) = O(n)
g(n) = O(2 n)
h(n) = O(5 n log n)
with the same comparison constant in all three cases
----------------------------------------------------
with a better English term instead of "comparison constant".
But I would simply write down the explicit inequalities.
f(n) = O(2) alone means exactly the same as f(n) = O(1), I think
you agree.
je
Josef Eschgfaeller <ยทยทยท@felix.unife.it> writes:
> Barry Margolin wrote:
>
> >> In mathematics O(1) = O(2) by definition. What means O(2) ... ?
>
> > I think that including the coefficient is intended to be useful
> > specifically when comparing algorithms that have the same complexity
> > without the coefficient.
>
> A mathematically correct notation for such simultaneous comparisons
> would be using vectors of functions, and perhaps to write
>
> (f(n), g(n), h(n)) = O(n, 2n, 5 n log n)
An even more mathematically correct notation would be to use
f(n) belongs to O(n)
with the appropriate symbol for 'belongs to' :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa