Big o list
Many problems in computing require the storage of a lot of pieces of information in some structure that allows the programmer to manage the structure, finding existing items, removing items, and adding new items. In choosing an appropriate structure, the programmer needs to consider how much space the structure will occupy, and how long it will take to carry out the common operations. If a lot of information must be stored, it is important to know how the time taken to manage the structure increases as the structure increases in size to accommodate more information. The behaviour of an algorithm as the data grow is typically described by Big O notation.
This table describes the behaviour of algorithms used to locate data, insert data, and delete data in commonly-used data structures.
Since software-users care not only about the typical behaviour of a piece of software, but also its worst behaviour when the data are as inconvenient as possible, and many algorithms (for example QuickSort, which is used to sort lists) have different Big-O behaviour in their worst-case, the table tabulates the normal performance and the worst-case scenario.
| Data Structure | Average behaviour | Worst Case behaviour | ||||||
|---|---|---|---|---|---|---|---|---|
| Space requirement | Locate an item | Insert item | Delete item | Space requirement | Locate an item | Insert item | Delete item | |
| k-d tree | O(n) | O(logn) | O(logn) | O(logn) | O(n) | O(n) | O(n) | O(n) |
| Association list | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) |
| Skip list | O(n) | O(log(n)) | O(log(n)) | O(log(n)) | O(n log(n)) | O(n) | O(n) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) |
See also
 |  |
