A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Sublinear algorithms solve problems in time (or space) less than the input size — they cannot even read the entire input. This is possible when approximate answers suffice and the algorithm can query specific parts of the input via random access or random sampling. A sublinear-time algorithm for estimating the average value of an array uses O(1/epsilon2) random samples to achieve epsilon-additive error with high probability, independent of array size. For graph problems, sublinear algorithms can estimate the number of connected components, approximate the minimum spanning tree weight, and test bipartiteness in time sublinear in the graph size. The key insight is that global properties often have local witnesses: if a property fails, a small random sample reveals evidence of failure with high probability.
Classical algorithm analysis assumes you read the entire input. But when the input is a petabyte-scale database, a social network with billions of edges, or a continuous data stream, reading everything is infeasible. Sublinear algorithms operate under the constraint that they see only a tiny fraction of the input, yet must provide useful (approximate) answers about global properties. The fundamental question is: which global properties leave enough local evidence that random sampling can detect them?
The simplest example is estimating the mean of an array. Drawing O(1/epsilon2) random samples and computing their average gives an estimate within epsilon additive error of the true mean, by the Chebyshev or Hoeffding inequality. This works for any array, regardless of size — the sample complexity depends only on the desired accuracy and confidence, not on n. The underlying principle is concentration of measure: the sample mean concentrates around the true mean. But not all statistics are this well-behaved. Estimating the median requires Omega(n) queries in the worst case, because a single hidden element can shift the median.
For graph problems, the story is richer. The number of connected components can be estimated in O(1/epsilon) time by sampling vertices and exploring their local neighborhoods via BFS. If a vertex's component has size less than 1/epsilon, the algorithm can determine this in O(1/epsilon) steps; otherwise, it contributes at most epsilon to the component count. Estimating the MST weight, testing bipartiteness, and approximating vertex cover all have sublinear algorithms with query complexity depending on the desired accuracy and graph structure. The query model matters: adjacency matrix queries (is edge (u,v) present?) versus adjacency list queries (what is the i-th neighbor of v?) yield different complexities for the same problem.
The theoretical foundations connect to property testing and communication complexity. Lower bounds for sublinear algorithms typically use Yao's minimax principle: construct two distributions on inputs (one with the property, one without) that cannot be distinguished by any algorithm making few queries. Information-theoretic arguments show that distinguishing these distributions requires a minimum number of queries. These lower bounds reveal which problems are fundamentally approachable in sublinear time and which resist it, painting a nuanced picture of what can be learned about massive datasets from limited observation.