    
  
  
   

Khái nim tim cn
Ký hiu– big-Oh (ca …)
Ký hiu– big-Omega (ca…)
Ký hiu– Theta (ca …)
 a  
Vi là  ln dliuu vào
T ltng trưng (chính xác):
+  +
 +
 log +  +
Bc tng trưng (xp x):
+  + => bc
 + => bc
 log +  + => bc log
!   "Ο-# $%&
- – big-Oh (chn trên – upper bound):
Ta nói rng ∈ ( ) nu tn ti các
hng s > 0, và > 0 sao cho:
0 ≤ ≤ 
vi mi ≥
Ví d: 2∈ ()( = 1, = 2)
Hàm không
phi giá tr
Ο-# $%#   ' '
- – big-Oh (chn trên – upper bound):
= { : tn ti các hng s > 0,
và > 0 sao cho:
0 ≤ ≤ 
vi mi ≥ }
Ví d: 2∈ ()