Subject: Re: [Boost-users] [Graph] Using a bit-based ajacency matrix.
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-03-01 11:27:17
AMDG
Thorsten Ottosen wrote:
> Steven Watanabe skrev:
>> Since when can you compute the bitwise and of an arbitrary
>> size bitset in constant time?
>
> Well, if the bitset size is less than or equal the word size.
That has nothing to do with big-O.
big-O describes an algorithm's asymptotic
behavior as the input becomes large.
> For larger sizes, the O(1/W * n ) complexity is also significantly
> better.
Last time I checked, O(constant * n) = O(n).
Yes, it's a lot faster, but it's faster by a constant factor.
In Christ,
Steven Watanabe