Algorithms & Complexity Flashcards
Grade 12 · Technology · Flashcards
Key terms, complexity classes, and algorithm design concepts for AP/college-level computer science review.
Flashcards
- Time Complexity
- A measure of how the runtime of an algorithm grows as the input size n increases, expressed using Big O notation.
- O(n log n)
- Linearithmic complexity; characteristic of efficient comparison-based sorting algorithms like merge sort and heap sort.
- Divide and Conquer
- Split problem into independent subproblems, solve recursively, merge results; examples include merge sort, quick sort, and binary search.
- Dynamic Programming
- Solve complex problems by breaking into overlapping subproblems and storing results; requires optimal substructure and overlapping subproblems.
- Greedy Algorithm
- Makes the locally optimal choice at each stage; correct for problems with the greedy-choice property (e.g., Huffman coding, Dijkstra's).
- Backtracking
- Systematically builds candidates and abandons branches violating constraints; used for constraint satisfaction, permutations, N-queens.
- P (Complexity Class)
- The set of decision problems solvable by a deterministic algorithm in polynomial time; considered tractable.
- NP (Complexity Class)
- The set of decision problems whose solutions can be verified in polynomial time by a deterministic algorithm.
- NP-Complete
- Problems that are both in NP and NP-hard; solving any one in polynomial time would imply P = NP. Examples: SAT, TSP, 3-coloring.
- Recurrence Relation
- Expresses runtime T(n) in terms of T on smaller inputs; e.g., T(n) = 2T(n/2) + O(n) for merge sort.
- Master Theorem
- Provides closed-form solutions to recurrences T(n) = aT(n/b) + f(n); widely used to analyze divide-and-conquer algorithms.
- Overlapping Subproblems
- A property where the same subproblems recur multiple times in a naive recursive solution; the key condition for DP applicability.
- Amortized O(1)
- Operations that occasionally cost O(n) but average out to O(1) over a long sequence; dynamic array append is the canonical example.
- Reduction
- Transforming one problem A into another problem B in polynomial time to prove A is at least as hard as B; central to NP-completeness proofs.
- Branch and Bound
- An optimization variant of backtracking that tracks the best solution found and prunes branches whose lower bound exceeds it.
Get a personalized course on Algorithms & Complexity built around your child.