"Limit definitions" of asymptotic (Bachmann-Landau) notation

88 Views Asked by At

This table has a column for "formal definitions" and another for "limit definitions" of the family of Bachmann-Landau notations.

What exactly are limt definitions and how do they relate to the formal definitions?

Since the notation is used to describe the asymptotic growth of functions, I thought the formal definitions were "limit" definitions themselves.

I'm especially not sure how the limit definitions for O, Ω and Θ are equivalent to their respective formal definitions. In the book Introduction to Algorithms, only the limit definition of Θ is given and it appears as a theorem (see Theorem 3.1)