[boost] Re: unions

From: David Abrahams (dave_at_[hidden])
Date: 2003-10-08 16:29:35

"E. Gladyshev" <egladysh_at_[hidden]> writes:

> --- David Abrahams <dave_at_[hidden]> wrote:
> [...]
>
>> As you nearly pointed out a few messages ago,
          ^^^^^^
>> O(N) == O(k * N).
>
> Don't put words in my mouth.  I did not say it.

I didn't say you said it!

> O(N) == O(k * N) is not right.

Please consult any basic textbook on algorithm complexity.  No offense
intended, but if we can't agree on O(N) == O(k * N), I think we'll
never agree on anything and I don't see any point in continuing this
conversation.

> k = N
> O(k*N) = O(N^2) != O(N)

k is the universal name for "any constant".  k = N is only true for
one particular N, and if we're looking only at that N, we have O(k*k)
== O(1).

See, you can prove anything if you're willing to be perverse enough.

o-n-squared-equals-o-one-ly y'rs,

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com