1/19
Comprehensive vocabulary flashcards covering sorting algorithms, hashing techniques, binary search tree operations, backtracking complexities, and comparison-based sorting bounds.
Quicksort
A comparison-based, in-place sorting algorithm with a best-case and average-case time complexity of Θ(nlog(n)), a worst-case time complexity of Θ(n2), and auxiliary space of O(log(n)) on average and O(n) in the worst case; it is not stable.
Pigeonhole Sort
A non-comparison sorting algorithm with a best, average, and worst-case time complexity of Θ(n+k), auxiliary space of O(k), which operates in-place and is not stable.
Counting Sort
A non-comparison sorting algorithm with a best, average, and worst-case time complexity of Θ(n+k) and auxiliary space of O(n+k); it is stable but not in-place.
Radix Sort
A non-comparison sorting algorithm with a best, average, and worst-case time complexity of Θ(d(n+k)) and auxiliary space of O(n+k) per pass; it is stable (Yes*) and not in-place.
Bucket Sort
A sorting algorithm with an expected best-case and average-case time complexity of Θ(n), a worst-case time complexity of O(n2), and auxiliary space of O(n+k); it is not in-place and its stability depends on the sorting algorithm used within the buckets.
Chaining (Separate Chaining)
A collision resolution technique with an expected time complexity of O(1+α) for search and delete, and O(1) for insert; a worst-case time complexity of O(n) for search, insert, and delete; and total space complexity of O(m+n).
Open Addressing
A collision resolution technique where all elements are stored directly within the hash table, having an expected time complexity of O(1) for search, insert, and delete; a worst-case time complexity of O(n); and total space complexity of O(m).
Binary Search Tree (BST) Dynamic-Set Operations
Operations on a binary search tree—including Search, Insert, Delete, Minimum, Maximum, Successor, and Predecessor—each possessing a time complexity of O(h), where h is the height of the tree.
Binary Search Tree Traversals
Tree traversal algorithms (Inorder traversal, Preorder traversal, and Postorder traversal) on a BST, each having a time complexity of Θ(n).
BST Sort
A sorting algorithm based on inserting elements into a binary search tree and performing an inorder traversal, running in O(nlog(n)) time when the tree is balanced and O(n2) time in the worst case.
Balanced Binary Search Tree
A tree structure with a height of O(log(n)) that achieves O(log(n)) time complexity for Search, Insert, and Delete operations.
Completely Skewed Binary Search Tree
A degenerate tree structure with a height of O(n) that degrades the time complexity of Search, Insert, and Delete operations to O(n).
Complete Subset Enumeration
A problem requiring the generation of all possible subsets, having a worst-case time complexity of Θ(2n) and an auxiliary space complexity of O(n) using Depth-First Search (DFS).
Sum of Subsets
A backtracking problem with a worst-case time complexity of O(2n) and an auxiliary space complexity of O(n).
0/1 Knapsack Backtracking
A backtracking algorithm that solves the 0/1 Knapsack problem with a worst-case time complexity of O(n2n) given an O(n) bound per node, requiring an auxiliary space complexity of O(n) for DFS depth.
State-Space Tree Leaf Count for Subsets
The structural property of subset problems where each item has two choices (include or exclude), resulting in a full state-space tree with 2n leaves and an exponential time complexity.
Comparison Sorting
A class of sorting algorithms (e.g., Quicksort) that determine order exclusively through pairwise comparisons; they are generally general-purpose with fewer input restrictions and are subject to a worst-case lower bound of Ω(nlog(n)).
Non-Comparison Sorting
A class of sorting algorithms (e.g., Counting Sort) that do not use pairwise comparisons, usually have more input restrictions, and can beat the Ω(nlog(n)) lower bound.
Comparison-Based Sorting Lower Bound
The theoretical bound of Ω(nlog(n)) derived from the decision-tree argument: because there are n! possible orderings of an input, a comparison decision tree must be capable of distinguishing at least n! distinct outcomes.
Radix Sort Linear Time Mechanism
The mechanism by which Radix Sort achieves linear time by processing information about digit positions instead of relying on pairwise comparisons between elements.