Subject: RE: [ippm] Comment on threshold on buffer sizes

From: Nischal M Piratla <[email-masked]>
Date: Tue, 8 Mar 2005 19:35:33 -0700

>Now wait: if I want to apply a metric offline, I will have to store N packets
>(or at least N sequence numbers) for ANY algorithm, requiring a buffer of
>O(N).

Given a sequence of numbers in a storage, the spatial complexity for that 
sequence is an absurd concept at the first place. Let it be reordering or 
anything else, one MUST not define spatial complexities on the data itself.

It is during the computation that we define spatial complexities. Many algos 
have spatial complexities, e.g., a certain sorting algo may have a spatial 
complexity of O(logN), i.e., during the computation, it will use a RAM of that 
order. Now, if numbers are in a hard disc or other media, do we say that the 
spatial complexity is N because we have these numbers somewhere? I probably 
missed a point here.

In addition, the computation complexities of ippm metrics will still be at a 
worst case order of O(N^2), due to comparisons associated with duplicate 
detections.

- Nischal

****************************************************
Research Assistant
Computer Networking Research Laboratory (CNRL)
C203,Dept. of Electrical & Computer Eng.
Colorado State University,
Fort Collins, CO 80523
Voice: 970-491-7067/7794
Fax:   970-491-2249
http://www.cnrl.colostate.edu
http://lamar.colostate.edu/~nischal
****************************************************

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

---

From: Henk Uijterwaal <[email-masked]>
Date: Wed, 09 Mar 2005 03:44:34 +0100

At 03:35 09/03/2005, Nischal M Piratla wrote:
>It is during the computation that we define spatial complexities.

Aha, that's what I missed.  I said this was for my own understanding :-)

Henk

>Many algos

------------------------------------------------------------------------------
Henk Uijterwaal                           Email: henk.uijterwaal(at)ripe.net
RIPE Network Coordination Centre          http://www.amsterdamned.org/~henk
P.O.Box 10096          Singel 258         Phone: +31.20.5354414
1001 EB Amsterdam      1016 AB Amsterdam  Fax: +31.20.5354445
The Netherlands        The Netherlands    Mobile: +31.6.55861746
------------------------------------------------------------------------------

Look here junior, don't you be so happy.
And for Heaven's sake, don't you be so sad.                 (Tom Verlaine)