Data Structures and Algorithms
Runtime
Array - Answer- Access: O(1)
Search: O(n)
Insertion: O(n)
Delete: O(n)
Stack - Answer- Access: O(n)
Search: O(n)
Insertion: O(1)
Delete: O(1)
Linked List (Singly and Doubly) - Answer- Access: O(n)
Search: O(n)
Insertion: O(1)
Delete: O(1)
Hash Table - Answer- O(1) for everything, but has no sorting
Binary Search Tree - Answer- Average O(log(n)) for everything, worst O(n) for
everything
Self-Balancing Trees (Red-Black, B, Splay, AVL) - Answer- Average and worst
O(log(n)) for everything
Quick Sort - Answer- Best: O(nlogn)
Average: O(nlogn)
Worst: O(n^2)
Space Worst: O(logn)
Merge Sort - Answer- Best: O(nlogn)
Average: O(nlogn)
Worst: O(nlogn)
Space Worst: O(n)
Bubble Sort - Answer- Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Space Worst: O(1)
Insertion Sort - Answer- Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Space Worst: O(1)
Selection Sort - Answer- Best: O(n^2)
Runtime
Array - Answer- Access: O(1)
Search: O(n)
Insertion: O(n)
Delete: O(n)
Stack - Answer- Access: O(n)
Search: O(n)
Insertion: O(1)
Delete: O(1)
Linked List (Singly and Doubly) - Answer- Access: O(n)
Search: O(n)
Insertion: O(1)
Delete: O(1)
Hash Table - Answer- O(1) for everything, but has no sorting
Binary Search Tree - Answer- Average O(log(n)) for everything, worst O(n) for
everything
Self-Balancing Trees (Red-Black, B, Splay, AVL) - Answer- Average and worst
O(log(n)) for everything
Quick Sort - Answer- Best: O(nlogn)
Average: O(nlogn)
Worst: O(n^2)
Space Worst: O(logn)
Merge Sort - Answer- Best: O(nlogn)
Average: O(nlogn)
Worst: O(nlogn)
Space Worst: O(n)
Bubble Sort - Answer- Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Space Worst: O(1)
Insertion Sort - Answer- Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Space Worst: O(1)
Selection Sort - Answer- Best: O(n^2)
