
Implementing Set Operations in Linear Time in Maple.Michael Monagan, Simon Fraser University
Abstract: Coding algorithms which do a sequence of insertions (or delections) into Maple sets or lists will generally lead to O(n^2) running time and O(n^2) space instead of O(n log n) time and O(n) space. This is because sets and lists are represented as arrays of pointers, and insertion and deletion in a Maple set or list costs O(n) time and space. In Maple, one can either hash tables or one can simulate linked lists to achieve linear time. I'll show how to do this on a basic operation for the graph theory package. 