Skip to main content
GameDev.net gamedev.net
🔒 Locked

Efficiency for various data structures

Started by BTownTKD Jan 27, 2006 at 8:23 AM 0 replies 450+ views
Original Post
BTownTKD
BTownTKD
Is there a website or someplace I can go to that has some type of library of big-O notations for aspects of a LOT of different data types? For instance, big-O notation for insertion at the front of a list for a singly-linked list, a doubly linked list, a stack, a queue, etc. Also, insertion at the back, deletion from the front, deletion from the back, deletion by index, etc. for all those same data types, and more. Basically, some kind of huge big-O notation table to compare and contrast the advantages and disadvantages of various data types.
Deep Blue Wave - Brian's Dev Blog.
SiCrane
SiCrane
A lot of those details are implementation specific even for the same kind of data structure. For example, length of a list could be O(n) or O(1) depending on the implementation. Pushing an element on one stack implementation could be O(1) average amortized, but O(n) worst case, and always O(1) for another implementation.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.