Time Complexity

A function g(x) is a member of O(f(x)) ("big oh of f") if there exist constants c and x₀ such that for all x ≥ x₀,

g(x) ≤ c f(x).
If g(x) is a member of O(f(x)), then g(x) has a growth rate no greater than the growth rate of f(x).
Two functions f(x) and g(x) have the same growth rate if
- f(x) is a member of O(g(x)), and
- g(x) is a member of O(f(x)).

Common Growth Rates

Growth Rate	Example
O(1)	Access array element
O(log₂ n)	Binary search
O(n)	Sequential search
O(n log₂ n)	Quick sort
O(n²)	Bubble sort
O(2ⁿ)	Factoring an integer
O(n!)	Traveling salesman problem

If the run time of an algorithm has a growth rate of O(f(x)) and it runs in t₀ seconds when the input size is n₀, then its run time is approximately

run time = c f(n) where c = t₀/f(n₀)

Example: Suppose an algorithm requires 1 second to execute when n = 100. The following tables show the estimated run times for various possible growth rates.

Input Size	O(1)	O(log₂ n)	O(n)	O(n log n)	O(n²)
10²	1 sec	1 sec	1 sec	1 sec	1 sec
10³	1 sec	1.5 sec	10 sec	15 sec	1.7 min
10⁴	1 sec	2 sec	1.7 min	3.3 min	2.8 hr
10⁵	1 sec	2.5 sec	17 min	42 min	11 days
10⁶	1 sec	3 sec	2.8 hr	8.3 hr	3.2 yr
10⁷	1 sec	3.5 sec	1.2 days	4.1 days	317 yr

Input Size	O(2ⁿ)
100	1 sec
110	17 min
120	12 days
130	34 yr
140	35,000 yr
150	36 million yr

Input Size	O(n!)
100	1 sec
101	1.7 min
102	2.9 hr
103	12 days
104	3.5 yr
105	367 yr
:	:
110	5.4 trillion yr

Example - BubbleSort.cpp

Return to Lectures page

This page was last modified on Feb 20, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/TimeComplexity.html