Tables
Here, each of the data structures already contain n number of elements. The tables show how the time taken for these operations to be excuted once will change as we increase the size of the data structure (i.e. n).
Retriveal refers to simly getting an element with it's key or index, if possible. If that is not possible for that data structure, then it looks through the structure (by traversal or otherwise) until it is found.
Big-O
Table showing the maximum possible running times for operations on data structures with n elements
| Add Element | Delete Element | Retrieve | Search | Traverse | |
|---|---|---|---|---|---|
| ArrayList(unsorted) | 1 | n | 1 | n | n |
| ArrayList(sorted) | n | n | logn | logn | n |
| LinkedList(unsorted) | 1 | n | n | n | n |
| HashTable(low load, balanced) | 1 | 1 | n | n | n |
| BST(unbalanced) | n | n | n | n | n |
| BST(balanced) | logn | logn | logn | logn | n |
Big-Ω
Table showing the minimum possible running times for operations on data structures with n elements
| Add Element | Delete Element | Retrieve | Search | Traverse | |
|---|---|---|---|---|---|
| ArrayList(unsorted) | 1 | 1 | 1 | 1 | n |
| ArrayList(sorted) | n | 1 | 1 | 1 | n |
| LinkedList(unsorted) | 1 | 1 | 1 | 1 | n |
| HashTable(low load, balanced) | 1 | 1? | 1 | 1 | n |
| BST(unbalanced) | 1 | 1 | 1 | 1 | n |
| BST(balanced) | logn | logn | logn | logn | n |
Big-Θ
Table showing the average running times for operations on data structures with n elements
| Add Element | Delete Element | Retrieve | Search | Traverse | |
|---|---|---|---|---|---|
| ArrayList(unsorted) | 1 | n | |||
| ArrayList(sorted) | n | n | |||
| LinkedList(unsorted) | n | ||||
| HashTable(low load, balanced) | 1 | 1? | n | ||
| BST(unbalanced) | n | ||||
| BST(balanced) | logn | logn | n |
Note: If a hash table uses a poor hash function, it will be and behave very much like a linked list, and so was not included in the table.
Note: The unbalanced BST basically has a linked list for the left child, and 1 node in the right sub-tree.