Little-o and Little-omega Notation

Math for CS · Axiom Academy

LESSON Little-o and Little-omega Notation Understand strict complexity bounds for algorithm analysis Little-o Notation: Strictly Less Than Little-o notation defines a STRICT upper bound. It's stronger than Big-O because the function grows strictly slower. Definition: means for every constant 0"> , there exists such that for all N"> Key Difference from Big-O: In Big-O, we allow . In little-o, we require for all constants , no matter how small. NOT true: (the function must be strictly slower!) Little-omega Notation: Strictly Greater Than Little-omega is the opposite of little-o—it defines a STRICT lower bound. The function grows strictly faster. Definition: means for every constant 0"> , there exists such that c g(n) 0"> for all N"> Relationship: is equivalent to Hierarchy (from smallest to largest): , is in between, and Practical Examples with Functions (true: grows faster than linear)

This is the written version of the interactive lesson above. See the full Math for CS course.