Re: [Boost-users] [Graph] Using a bit-based ajacency matrix.

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