Avg. Access Array
O(1)
Avg. Search Array
0(n)
Avg. Insertion Array
O(n)
Avg. Deletion Array
O(n)
Avg. Access Singly Linked List
O(n) - have to loop to n
Avg. Search Singly Linked List
O(n) - have to loop to n
Avg. Insertion Singly Linked List (insert @ end)
O(1) - add a new node/ append to end
Avg. Insertion Singly Linked List (insert @ index)
O(n) - have to loop to index, then insert value
Avg. Delete Singly Linked List (delete @ end)
O(1) - delete the end node
Avg. Delete Singly Linked List (delete @ index)
O(n) - have to loop to index, then delete value
Hash Table Access
O(1)
Hash Table Search
O(1)
Hash Tabe Insert
O(1)
Hash Table Delete
O(1)
Adavantages of Linked List
- have a constant insert and delete (only at ends)
- good if you don’t know how many items are in list
- if you don’t need random access
- you need to insert in the middle of a list.
Dis advantages of Linked List
- no random access
- if you know the number of elements in the list ahead
of time - memory is a concern (Linked lists require pointers to next data value. While arrays just store the value itself
- need speed to iterate through a list
Find in Binary Search Tree (best)
O(1) - item is located at the root
Find in Binary Search Tree (avg)
O(log n) - divides amount of work each time by 2
Find in Binary Search Tree (worst)
O(n) - this is in the case that tree isn’t balanced, or the shape is irregular. So the tree could go through many uncessary steps
Find in Balanced Binary Search (best)
O(1) - item is located at the root
Find in Balanced Binary Search (avg)
O(log n)
Find in Balanced Binary Search (worst)
O(log n)
Equation to determine if BST is balanced
heightOfLeftSideOfTree - heightOfRightSideOfTree = 1
