Time complexity

Time complexity describes how an algorithm’s running time grows with input size, usually through an asymptotic function that abstracts away machine-specific details.

Asymptotic analysis: The study of how functions behave as their inputs grow without bound. It turns running-time measurements into statements about growth at large input sizes.
Algorithm: A finite, well-defined procedure for solving a problem or performing a computation. Time complexity is a property assigned to an algorithm’s execution.
Space complexity: The amount of memory an algorithm requires as a function of input size. It tracks memory use rather than computational time.
Binary search: A search algorithm that repeatedly halves a sorted range to locate a target. Its logarithmic running time illustrates the benefit of reducing the search range by half.
P versus NP problem: The open question of whether every problem whose solution can be verified quickly can also be solved quickly. It asks whether a broad class of problems has polynomial-time algorithms.
Big O notation: Notation that gives an asymptotic upper bound on a function’s growth. It expresses an upper bound on an algorithm’s running-time growth.
Input size: A measure of the amount of data supplied to a computational problem. It is the variable against which an algorithm’s running time is expressed.
Best-case complexity: The minimum cost an algorithm incurs among inputs of a specified size. It contrasts with worst-case bounds by considering the easiest inputs.
Merge sort: A comparison sorting algorithm that divides a list, sorts its parts, and merges them. Its O(n log n) running time exemplifies divide-and-conquer analysis.
Fine-grained complexity: The study of precise running-time bounds and conditional limits on algorithmic improvements. It investigates whether known time bounds can be improved by even modest factors.

Linked from 19 pages