Big-O Notation

Definition

Big-O notation describes how an algorithm’s time or space usage grows as the size of the input grows. It does not focus on exact runtime in seconds; it focuses on growth rate and relative scalability.

---

Core Ideas

What It Measures

• time complexity — how runtime grows
• space complexity — how memory usage grows

Common Orders of Growth

• O(1) — constant time
• O(log n) — logarithmic
• O(n) — linear
• O(n log n) — common for efficient sorting
• O(n^2) — quadratic
• O(2^n) or O(n!) — explosive growth

Why It Matters

Big-O helps compare algorithmic trade-offs without being trapped by machine speed, framework overhead, or constant factors. It is especially useful when input size may become large.

Limits

Big-O is not the whole story:

• constants still matter in practice
• typical-case behavior can matter more than worst case for some workloads
• system design bottlenecks often come from I/O, network, or data access patterns, not just pure algorithmic complexity

---

Relationships

• Software Engineering Practices — algorithmic thinking is one layer of engineering quality
• System Design — large-scale systems combine algorithmic efficiency with data, network, and caching trade-offs

---

References

• 常用算法Big-O复杂度介绍（时间和空间复杂度）
• _Best Practice of Software Engineering and Architecture