Performance and Complexity

[sugaurav]

Hi Marian,

First of all, thanks for this header based project.

Can i get some data from performance & complexity analysis done on the project. Like how much time sglib takes for addition, deletion, search & delete for say N no. of data records.

Also, does all the complexities of algorithms in sglib concides with standard complexities of data structures.

Thanks,
Sushant Gaurav

[Marian-Vittek]

Hi Sushant,

Can i get some data from performance & complexity analysis done on the project. Like how much time sglib takes for addition, deletion, search & delete for say N no. of data records.
Also, does all the complexities of algorithms in sglib concides with standard complexities of data structures.

I don't have any measured data or complexity analysis. The complexity of the data structures used is well known and sglib implements them in a standard way. In other words:

• Add/delete/search in linear sorted lists is proportional to the length of the list, i.e. O(n). Same for non sorted list, except that add is O(1).
• Add/search in double linked sorted lists is O(n), deletion is O(1) if you have a pointer to the element to be deleted. Same for non sorted list , except that add is O(1).
• Add/delete/search on a red-black tree is O(log n).
• As for hash tables, the estimation is tricky (just like hash tables are). Strictly theoretically, the complexity of a fixed sized hash table is the same as the complexity of the underlying base container. The hash table provides "only" a constant factor improvement.

Concerning sorting algorithms, sglib provides quicksort and heapsort for arrays and mergesort for linked lists. Quicksort has the worst case performance O(n^2), heapsort and mergesort both have the worst case complexity O(n * log n).

I hope this answers your question,

Marian