Algorithms, Data Structures, and Complexity Analysis

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/19

flashcard set

Earn XP

Description and Tags

Comprehensive vocabulary flashcards covering sorting algorithms, hashing techniques, binary search tree operations, backtracking complexities, and comparison-based sorting bounds.

20 Terms

1
New cards

Quicksort

A comparison-based, in-place sorting algorithm with a best-case and average-case time complexity of Θ(nlog⁡(n))\Theta(n \log(n)), a worst-case time complexity of Θ(n2)\Theta(n^2), and auxiliary space of O(log⁡(n))O(\log(n)) on average and O(n)O(n) in the worst case; it is not stable.

2
New cards

Pigeonhole Sort

A non-comparison sorting algorithm with a best, average, and worst-case time complexity of Θ(n+k)\Theta(n + k), auxiliary space of O(k)O(k), which operates in-place and is not stable.

3
New cards

Counting Sort

A non-comparison sorting algorithm with a best, average, and worst-case time complexity of Θ(n+k)\Theta(n + k) and auxiliary space of O(n+k)O(n + k); it is stable but not in-place.

4
New cards

Radix Sort

A non-comparison sorting algorithm with a best, average, and worst-case time complexity of Θ(d(n+k))\Theta(d(n + k)) and auxiliary space of O(n+k)O(n + k) per pass; it is stable (Yes*) and not in-place.

5
New cards

Bucket Sort

A sorting algorithm with an expected best-case and average-case time complexity of Θ(n)\Theta(n), a worst-case time complexity of O(n2)O(n^2), and auxiliary space of O(n+k)O(n + k); it is not in-place and its stability depends on the sorting algorithm used within the buckets.

6
New cards

Chaining (Separate Chaining)

A collision resolution technique with an expected time complexity of O(1+α)O(1 + \alpha) for search and delete, and O(1)O(1) for insert; a worst-case time complexity of O(n)O(n) for search, insert, and delete; and total space complexity of O(m+n)O(m + n).

7
New cards

Open Addressing

A collision resolution technique where all elements are stored directly within the hash table, having an expected time complexity of O(1)O(1) for search, insert, and delete; a worst-case time complexity of O(n)O(n); and total space complexity of O(m)O(m).

8
New cards

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)O(h), where hh is the height of the tree.

9
New cards

Binary Search Tree Traversals

Tree traversal algorithms (Inorder traversal, Preorder traversal, and Postorder traversal) on a BST, each having a time complexity of Θ(n)\Theta(n).

10
New cards

BST Sort

A sorting algorithm based on inserting elements into a binary search tree and performing an inorder traversal, running in O(nlog⁡(n))O(n \log(n)) time when the tree is balanced and O(n2)O(n^2) time in the worst case.

11
New cards

Balanced Binary Search Tree

A tree structure with a height of O(log⁡(n))O(\log(n)) that achieves O(log⁡(n))O(\log(n)) time complexity for Search, Insert, and Delete operations.

12
New cards

Completely Skewed Binary Search Tree

A degenerate tree structure with a height of O(n)O(n) that degrades the time complexity of Search, Insert, and Delete operations to O(n)O(n).

13
New cards

Complete Subset Enumeration

A problem requiring the generation of all possible subsets, having a worst-case time complexity of Θ(2n)\Theta(2^n) and an auxiliary space complexity of O(n)O(n) using Depth-First Search (DFS).

14
New cards

Sum of Subsets

A backtracking problem with a worst-case time complexity of O(2n)O(2^n) and an auxiliary space complexity of O(n)O(n).

15
New cards

0/1 Knapsack Backtracking

A backtracking algorithm that solves the 0/1 Knapsack problem with a worst-case time complexity of O(n2n)O(n 2^n) given an O(n)O(n) bound per node, requiring an auxiliary space complexity of O(n)O(n) for DFS depth.

16
New cards

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 2n2^n leaves and an exponential time complexity.

17
New cards

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))\Omega(n \log(n)).

18
New cards

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))\Omega(n \log(n)) lower bound.

19
New cards

Comparison-Based Sorting Lower Bound

The theoretical bound of Ω(nlog⁡(n))\Omega(n \log(n)) derived from the decision-tree argument: because there are n!n! possible orderings of an input, a comparison decision tree must be capable of distinguishing at least n!n! distinct outcomes.

20
New cards

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.