[Data-modeling] Modeling datastructures

[Tim Kientzle]

> To summarize, this is what we'd have:
>
> Type: Big O Order (or whatever you want to name it)
> Display: Enumerated
> Properties:
> 1) Data structures with this space complexity (expected type: Data
> Structure)
> 2) Algorithms with this runtime efficiency (expected type: Algorithm)
> Create a topic for each common order: O(1), O(n), O(log n), O(n log  
> n),
> O(n^2), etc.

Actually, there are at least two different complexity measures for
each operation on a data structure.[1]

So I think you'll need at least a type for operations, another for
data structures, and a CVT which attaches a complexity to each
combination.

E.g.,
   array <---  O(n) space ---> Merge sort
   array <---  O(n log n) time ---> Merge sort
   linked list <--- O(1) space ---> Merge sort
   linked list <--- O(n log n) time ---> Merge sort
   heap <---  O(n) space ---> inserting n items
   heap <---  O(n log n) time ---> inserting n items
   heap <---  O(n log n) time ---> removing first n items

Of course, as David pointed out, "n" is a pretty simple case.
Complexity often varies with several features (average link
density, tree height, largest clique).

Stepanov's STL work at SGI (http://www.sgi.com/tech/stl/)
has resulted in a very nice hierarchy of data structures
and operations that seems like a nice starting point for this.

Tim

[1] Of course, this is only if you limit yourself to big-O
asymptotic average complexity.  There are quite a few
other complexity measures that are of interest in various cases.