Asymptotic Notations
Asymptotic notations are mathematical tools used to describe the efficiency and scalability of algorithms as input size increases.
The Big Three: 1. Big O (O): Upper bound (Worst Case). 2. Big Omega (Ω): Lower bound (Best Case). 3. Big Theta (Θ): Tight bound (The algorithm is nested between the two). Other classes: O(1) - Constant, O(log n) - Logarithmic, O(n) - Linear, O(n log n) - Linearithmic, O(n^2) - Quadratic, O(2^n) - Exponential.
graph LR
Center["Asymptotic Notations"]:::main
Pre_networking["networking"]:::pre --> Center
click Pre_networking "/terms/networking"
Rel_decentralization["decentralization"]:::related -.-> Center
click Rel_decentralization "/terms/decentralization"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 5살도 이해할 수 있게 설명
Imagine you're comparing how fast people can clean a house. One person cleans 1 room an hour (constant). Another person cleans faster the more people help them (linear). Asymptotic notation is like a score that tells you how the cleaning time changes if the house suddenly becomes a giant castle with a million rooms.
🤓 Expert Deep Dive
Formally, a function f(n) is O(g(n)) if there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0. These notations ignore constant coefficients and lower-order terms to focus on the 'Growth Class' (e.g., O(log n), O(n), O(n^2)). Understanding the tight bound (Big Theta) is critical for definitive performance guarantees, while Little o and Little omega are used in advanced complexity theory to denote bounds that are strictly smaller or larger than the function's growth.