Questions and Answers
What is the best runtime of Bubble Sort?
O(n)
What is the worst runtime of Bubble Sort?
O(n^2)
What is the average runtime of Bubble Sort?
O(n^2)
What is the best runtime of Selection Sort?
Signup and view all the answers
What is the worst runtime of Selection Sort?
Signup and view all the answers
What is the average runtime of Selection Sort?
Signup and view all the answers
What is the best runtime of Insertion Sort?
Signup and view all the answers
What is the worst runtime of Insertion Sort?
Signup and view all the answers
What is the average runtime of Insertion Sort?
Signup and view all the answers
What are the worst and average runtimes of Linear Probing, Quadratic Probing, and Separate Chaining Insertion?
Signup and view all the answers
What are the worst and average runtimes of Linear Probing, Quadratic Probing, and Separate Chaining Search/Retrieval?
Signup and view all the answers
What is the equation for Linear Probing?
Signup and view all the answers
What is the equation for Quadratic Probing?
Signup and view all the answers
What are the worst and best runtimes for Trie Insertion?
Signup and view all the answers
What are the worst and best runtimes for Trie Search?
Signup and view all the answers
What are the worst and best runtimes for Trie Deletion?
Signup and view all the answers
What are the worst case runtimes for AVL Tree Search, Insertion and Deletion?
Signup and view all the answers
What are the worst case runtimes for BST Search, Insertion, and Deletion?
Signup and view all the answers
What is the best case runtime for BST Search, Insertion, and Deletion?
Signup and view all the answers
What are the best case runtimes for AVL Tree Search, Insertion and Deletion?
Signup and view all the answers
What type of data structure works best for Merge Sort?
Signup and view all the answers
What are the best, average, and worst runtimes for Merge Sort?
Signup and view all the answers
What is the pattern for INORDER tree traversals?
Signup and view all the answers
What is the pattern for PREORDER tree traversals?
Signup and view all the answers
What is the pattern for POSTORDER tree traversals?
Signup and view all the answers
Study Notes
Bubble Sort
- Best runtime: O(n) - achieved when the input is already sorted.
- Worst runtime: O(n^2) - occurs with reverse-sorted inputs.
- Average runtime: O(n^2) - reflects inefficient comparisons in unsorted data.
Selection Sort
- Best runtime: O(n^2) - selection sort always requires O(n^2) time regardless of input.
- Worst runtime: O(n^2) - consistent performance under different conditions.
- Average runtime: O(n^2) - no variation in efficiency across random inputs.
Insertion Sort
- Best runtime: O(n) - optimal for nearly sorted data, performs minimal shifts.
- Worst runtime: O(n^2) - occurs with completely unsorted lists, requiring maximum shifts.
- Average runtime: O(n^2) - generally inefficient for larger data sets.
Hash Table Probing
- Worst & average runtime for insertion: Worst = O(n), Average = O(1) across Linear Probing, Quadratic Probing, and Separate Chaining.
- Worst & average runtime for search/retrieval: Worst = O(n), Average = O(1) similarly applies.
Probing Equations
- Linear probing index equation: index = (hVal + i) % h->TABLE_SIZE.
- Quadratic probing index equation: index = (hVal + i * i) % h->TABLE_SIZE.
Trie Data Structure
- Insertion: Worst & Best runtimes are O(k), with k being the length of the key.
- Search: Worst = O(k), Best = O(1).
- Deletion: Worst = O(k), Best = O(1).
AVL and Binary Search Trees (BST)
- AVL Tree operations (search, insertion, deletion): Worst case runtime is O(log n).
- BST operations: Worst case runtime is O(n) due to potential degenerative structure.
- Best case for BST operations: O(log n) when tree is balanced.
Merge Sort
- Best, average, and worst runtimes: O(n log n) - efficient across different scenarios.
- Best data structure for implementation: Linked Lists, allowing seamless merging.
Tree Traversals
- Inorder traversal pattern: Traverse Left, then Root, then Right.
- Preorder traversal pattern: Visit Root, then Left, then Right.
- Postorder traversal pattern: Traverse Left, then Right, then Root.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Explore the characteristics and performance of various sorting algorithms, including Bubble Sort, Selection Sort, and Insertion Sort. Additionally, the quiz covers hash table probing techniques and their respective runtimes. Test your understanding of these fundamental algorithms and data structures.
