Algorithm: A finite list of steps that solves a problem
Big-O notation: Describes how running time or memory grows as input grows
O(1): Constant time; stays the same as input grows
O(log n): Logarithmic time; grows slowly, like binary search
O(n): Linear time; grows in proportion to input size
O(n log n): Typical of efficient sorting like merge sort
O(n squared): Quadratic time; typical of simple nested loops
O(2 to the n): Exponential time; becomes huge very quickly
Time complexity: How running time grows with input size
Space complexity: How memory use grows with input size
Linear search: Check each item in order until found; O(n)
Binary search: Repeatedly halve a sorted list to find an item; O(log n)
Binary search requirement: The data must be sorted
Bubble sort: Repeatedly swaps adjacent items that are out of order; O(n squared)
Selection sort: Repeatedly picks the smallest item and places it first; O(n squared)
Insertion sort: Builds a sorted list one item at a time; good for small or nearly sorted lists
Merge sort: Splits the list, sorts the halves, then merges; O(n log n)
Quick sort: Picks a pivot and partitions around it; average O(n log n)
Heap sort: Sorts using a heap; O(n log n)
Pivot: The element used to partition in quick sort
Stable sort: A sort that keeps equal items in their original order
Divide and conquer: Split a problem, solve the parts, combine the answers
Recursion: A function calling itself on smaller input
Base case: The stopping point of a recursion
Dynamic programming: Solve overlapping subproblems once and store the results
Memoization: Caching results of function calls
Greedy algorithm: Pick the best choice at each step
Brute force: Try every possibility
Backtracking: Try choices and undo them when they fail
Breadth-first search (BFS): Explore a graph level by level using a queue
Depth-first search (DFS): Explore a graph as deep as possible using a stack or recursion
Dijkstra's algorithm: Finds shortest paths in a weighted graph with non-negative weights
A* search: A pathfinding algorithm that uses a guess of distance to the goal
Minimum spanning tree: A tree connecting all nodes with smallest total weight
Kruskal's and Prim's: Algorithms for finding minimum spanning trees
Topological sort: Ordering tasks so each comes after its prerequisites
Hashing: Turning data into a fixed-size number for fast lookup
Collision: When two keys hash to the same spot
Euclid's algorithm: Finds the greatest common divisor using repeated remainders
Sieve of Eratosthenes: Finds all primes up to a number by crossing out multiples
Fibonacci sequence: Each number is the sum of the two before: 0, 1, 1, 2, 3, 5...
Factorial: n! is the product of all whole numbers from 1 to n
Tower of Hanoi: A puzzle that is a classic recursion example
Traveling salesman problem: Find the shortest route visiting every city once; very hard
NP-complete: A class of hard problems with no known fast solution
P vs NP: A famous open question about whether hard-to-solve problems are also easy to check
Heuristic: A practical shortcut that finds a good answer, not always the best
Pseudocode: Plain-language description of an algorithm
Invariant: A condition that stays true during an algorithm
Best case: The fastest an algorithm can run
Worst case: The slowest an algorithm can run
Average case: Typical running time over many inputs
In-place algorithm: Uses very little extra memory
Two pointers: A technique using two positions that move through data
Sliding window: A technique moving a fixed range along data
PageRank: Google's algorithm that ranks pages by links to them
Compression algorithm: Makes data smaller, like ZIP or JPEG
Lossless compression: Compression that can be exactly reversed
Lossy compression: Compression that discards some data, like JPEG
Random number generator: An algorithm that makes numbers that look random
Machine learning algorithm: An algorithm that learns patterns from data
Al-Khwarizmi: Persian mathematician whose name gave us the word algorithm
Algorithm origin: Named after a 9th-century scholar al-Khwarizmi

Free flashcards from Peabody at peabody.kids/flashcards/tech-algorithms