Big-O は input size n が増えるにつれて、algorithm の running time や memory がどう増えるかを表します。constants と lower-order terms を無視し、主に worst-case の asymptotic behavior を捉えます。
正確な step count ではなく growth rate を見ます。O(2n + 5) は O(n) です。n が大きくなると constant と小さい term は重要でなくなるからです。
| Big-O | Name | Example |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scanning a list |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | nested loops |
| O(2ⁿ) | exponential | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O は constants を隠します。huge constant を持つ O(n) algorithm が、small input では O(n log n) に負けることもあります。time だけでなく space complexity も追跡します。
Big-O は hardware や実行なしに algorithm を比較する言語です。input が hundreds から millions に増えたとき、どの solution が scale し、どれが timeout するかを予測できます。performance を考える全 engineer の vocabulary です。