Subject: [ippm] spatial complexity of n-reordering

From: stanislav shalunov <[email-masked]>
Date: 07 Mar 2005 21:40:06 -0500

Since I didn't have enough time at the mike to make this comment and
Henk suggested I send this to the list:

Nischal's slides (not sure about the number) have a table that
summarize spatial complexity of various metrics.  The table claims
O(N) for n-reordering, where N, I presume, is the sample size.  The
actual complexity is O(1).

-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

All revolutions are bloody.  The October Revolution was bloodless,
but it was only the beginning.               -- Dmitri Volkogonov

_______________________________________________
ippm mailing list
[email-masked] 
https://www1.ietf.org/mailman/listinfo/ippm

---

From: stanislav shalunov <[email-masked]>
Date: 08 Mar 2005 00:51:26 -0500

stanislav shalunov <[email-masked]> writes:

> O(N) for n-reordering, [...]  The actual complexity is O(1).

It was pointed out to me that I forgot to mention that the temporal
complexity is O(N) rather than O(N^2) (as the table in Nischal's
slides had it).

Clothes make the man.  Naked people have little or no influence on
society.                                             -- Mark Twain