Big O Notation
Big O notation describes how an algorithm's running time or memory use grows as the input gets larger, ignoring constant details. For example, O(n) grows in direct proportion to the input.
General Programming
It lets you compare algorithms independently of hardware. Common complexities, from fastest to slowest, include O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), and O(n^2) quadratic.
A loop over n items is O(n); a loop inside a loop over the same items is O(n^2).
Examples
Python
# O(n): one pass over n items
def contains(items, target):
for item in items:
if item == target:
return True
return False
print(contains([3, 7, 9], 7))Output:
True