Technical Glossary

A

Amortized Analysis

A method of analyzing algorithm complexity that averages cost over a sequence of operations, even if a single operation is expensive. Example: dynamic array append is O(1) amortized despite occasional O(n) resizing.

AVL Tree

A self-balancing binary search tree where the height difference between left and right subtrees of any node is at most 1. Guarantees O(log n) search, insert, and delete.

B

Backtracking

A recursive algorithmic technique that builds candidates incrementally and abandons ('backtracks') a candidate as soon as it determines the candidate cannot lead to a valid solution. Used in N-Queens, Sudoku, and permutation generation.

BFS (Breadth-First Search)

A graph traversal algorithm that explores all neighbors at the current depth before moving to the next level. Uses a queue. Finds shortest path in unweighted graphs. Time: O(V+E).

Big-O Notation

A mathematical notation describing the upper bound of an algorithm's growth rate. O(n) means linear growth, O(n²) means quadratic. Used to compare algorithm efficiency independent of hardware.

Binary Search

An efficient search algorithm for sorted arrays that repeatedly divides the search interval in half. Time: O(log n). Requires random access (arrays, not linked lists).

Binary Tree

A tree data structure where each node has at most two children (left and right). Special variants: BST (ordered), complete, full, perfect, and balanced trees.

Bloom Filter

A space-efficient probabilistic data structure that tests whether an element is in a set. May have false positives but never false negatives. Used in databases, caches, and web crawlers.

C

CAP Theorem

In distributed systems, you can guarantee at most two of three properties: Consistency, Availability, and Partition tolerance. Systems must choose CP (consistent but may be unavailable) or AP (available but may be stale).

Consistent Hashing

A hashing technique used in distributed systems where adding or removing a server only requires remapping K/n keys (K = total keys, n = servers). Used in load balancing, distributed caches, and database sharding.

D

DFS (Depth-First Search)

A graph traversal algorithm that explores as far as possible along each branch before backtracking. Uses a stack (or recursion). Time: O(V+E). Used for cycle detection, topological sort, and pathfinding.

Dynamic Programming

An optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each once, and storing results (memoization or tabulation). Examples: Fibonacci, Knapsack, LCS.

G

Graph

A non-linear data structure consisting of vertices (nodes) and edges connecting them. Can be directed or undirected, weighted or unweighted. Represented as adjacency list or adjacency matrix.

Greedy Algorithm

An approach that makes the locally optimal choice at each step, hoping to find the global optimum. Works when the greedy choice property and optimal substructure hold. Examples: Dijkstra's, Huffman coding, activity selection.

H

Hash Collision

When two different keys map to the same index in a hash table. Resolved via chaining (linked lists at each bucket) or open addressing (probing to find the next empty slot).

Hash Map (Hash Table)

A data structure that stores key-value pairs with O(1) average access, insert, and delete. Uses a hash function to map keys to array indices. Java: HashMap, Python: dict.

Heap (Priority Queue)

A complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children. Insert and extract-min/max in O(log n). Used in Dijkstra's, top-K problems, and merge-K-sorted.

I

In-place Algorithm

An algorithm that transforms input using only a constant amount of extra space (O(1)). The input array itself is modified. Examples: in-place quicksort, array reversal.

L

Linked List

A linear data structure where elements (nodes) are connected via pointers. Singly linked (next only) or doubly linked (next + prev). O(1) insert/delete at known position, O(n) access.

Load Balancer

A system component that distributes incoming network traffic across multiple servers. Strategies: round-robin, least connections, IP hash, weighted. Improves availability and throughput.

M

Memoization

A top-down dynamic programming technique that stores the results of expensive function calls and returns the cached result when the same inputs occur again. Implemented using hash maps or arrays.

Merge Sort

A stable, divide-and-conquer sorting algorithm. Recursively splits the array in half, sorts each half, then merges. Time: O(n log n) always. Space: O(n). Preferred when stability matters.

Monotonic Stack

A stack that maintains elements in sorted (increasing or decreasing) order. Used to efficiently find the next greater/smaller element. Time: O(n) for the entire array.

N

NP-Hard

A class of computational problems for which no known polynomial-time algorithm exists. NP-complete problems (e.g., Traveling Salesman, 3-SAT) are both NP and NP-hard. Often solved with approximation or heuristics.

Q

Quick Sort

A divide-and-conquer sorting algorithm that selects a pivot, partitions elements around it, and recursively sorts partitions. Average O(n log n), worst O(n²). In-place, not stable. Fastest in practice.

R

Rate Limiting

A technique to control the rate of requests a client can make to a service. Algorithms: token bucket, sliding window log, sliding window counter, fixed window. Prevents abuse and ensures fairness.

Red-Black Tree

A self-balancing BST where each node has a color (red or black) and the tree satisfies properties that ensure O(log n) height. Used internally by Java TreeMap, C++ std::map.

Recursion

A technique where a function calls itself to solve smaller instances of the same problem. Requires a base case to terminate. Every recursive solution can be converted to an iterative one using a stack.

S

Sharding

Splitting a database into smaller, independent pieces (shards) distributed across servers. Each shard holds a subset of data. Improves write throughput and storage capacity. Challenges: cross-shard queries, rebalancing.

Sliding Window

A technique for processing subarrays/substrings by maintaining a window that expands and shrinks. Fixed window: size stays constant. Variable window: expands right, shrinks left when constraint violated.

Space Complexity

The amount of memory an algorithm uses relative to input size. Includes auxiliary space (extra space) but often excludes input. O(1) = constant, O(n) = linear, O(n²) = quadratic.

Stable Sort

A sorting algorithm that preserves the relative order of elements with equal keys. Merge sort and insertion sort are stable; quicksort and heapsort are not. Matters when sorting by multiple criteria.

Stack

A LIFO (Last In, First Out) data structure. Push and pop in O(1). Used in DFS, expression evaluation, undo systems, and monotonic stack patterns. Java: Deque (ArrayDeque); Python: list.

T

Tabulation

A bottom-up dynamic programming technique that fills a table iteratively from base cases up to the desired answer. Avoids recursion overhead. Often more space-efficient than memoization.

Time Complexity

A measure of how an algorithm's running time grows relative to input size. Expressed in Big-O notation. O(n log n) is typical for efficient sorting; O(n²) is quadratic and often too slow for n > 10,000.

Topological Sort

A linear ordering of vertices in a DAG (directed acyclic graph) such that for every edge u→v, u comes before v. Used in dependency resolution, build systems, course scheduling. Kahn's algorithm or DFS-based.

Trie (Prefix Tree)

A tree data structure for storing strings where each node represents a character. Enables O(L) search, insert, and prefix lookup (L = string length). Used in autocomplete, spell check, and IP routing.

Two Pointers

A technique using two indices that move through a data structure (usually a sorted array) to find pairs or subarrays satisfying a condition. Reduces O(n²) brute force to O(n). Examples: two sum in sorted array, container with most water.

U

Union-Find (Disjoint Set)

A data structure that tracks elements partitioned into disjoint sets. Supports union (merge sets) and find (determine set membership) in near O(1) with path compression and union by rank. Used for connected components and Kruskal's MST.

V

Vector Database

A database optimized for storing and querying high-dimensional vectors (embeddings). Supports approximate nearest neighbor (ANN) search. Used in RAG, recommendation systems, and similarity search. Examples: Pinecone, Weaviate, Milvus.

W

WebSocket

A communication protocol providing full-duplex channels over a single TCP connection. Unlike HTTP (request-response), WebSockets allow the server to push data to the client. Used in real-time chat, live feeds, and collaborative editing.

A