Data Structures and Algorithms Runtime Questions with Answers

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) Average: O(n^2)