Quadratic Time
Runtime that grows with the square of input size.
Formula
Variables
Example
Bubble sort
How it works
O(n^2) means the running time increases roughly with the square of the input size, so doubling the input can make the work about four times larger. This usually happens when an algorithm has two nested loops over the same data, or when every item must be compared with many other items. The square growth comes from counting all pairwise or near-pairwise operations, which quickly becomes expensive as n gets bigger.
When to use it
Use this to describe algorithms that repeatedly compare elements against many others, such as checking every pair in a list or doing a full scan inside another full scan. It is common in basic sorting, matrix-style loops, and simple brute-force search over pairs.
Worked example, step by step
Suppose an algorithm does 5n^2 basic operations. Let n = 3. Step 1: Square the input size: 3^2 = 9. Step 2: Multiply by 5: 5 × 9 = 45. Final answer: the runtime is proportional to 45 basic operations, so the algorithm follows O(n^2) growth.
Common mistakes to avoid
- Thinking O(n^2) means the exact number of operations is n^2, instead of an upper growth trend
- Forgetting that a constant multiplier like 5 or 100 is ignored in Big-O notation
- Assuming any two loops automatically make an algorithm O(n^2) even when the loops do not both scale with n
Did You Know?
Quadratic algorithms crawl on big data: sorting a million items the naive way takes a trillion comparisons.
Share this formula
More in Computer Science
View allShannon Entropy
AdvancedAverage information content of a random source (bits).
Master Theorem (form)
AdvancedAnalyzes running time of divide-and-conquer algorithms.
Hamming Distance
AdvancedNumber of positions at which two strings differ.
Bits to Represent n
BasicMinimum number of bits to represent n distinct values.
Binary to Decimal
BasicConverts a binary number to decimal.
Nodes in a Full Binary Tree
IntermediateTotal nodes in a perfect binary tree of height h.