_{References used for this section: A}

**Asymptotic Analysis**

** – notation**

Definition: there exist positive constants and such that for all .

Note on abuse of notation: If a function satisfies the above condition, it is an element of . In standard notation, this should be written as … but fuck standard notation, we’re computer scientists. So we choose to abuse the notation by writing it as . This is useful.

** – notation**

Definition: there exist positive constants and such that for all .

We abuse the notation for the same way as we do for (refer to the note above).

Since notation is a stronger notion than notation, it is evident that implies . In other words, .

** – notation**

Definition: there exist positive constants and such that for all .

Once again, we abuse – notation the same way as the above two.

Theorem: For any two functions and , we have if and only if and .

This figure kind of summaries the above three notations:

** – notation**

Definition: for any positive constant there exists a constant such that for all .

This is very similar to notation. This example illustrates a key difference:

and however, but . In other words, we use notation for upper bounds that are not *asymptotically tigh**t*.

** – notation**

Definition: for any positive constant there exists a constant such that for all .

This is very similar to notation. This example illustrates a key difference:

and . However, but . In other words, we use notation for lower bounds that are not *asymptotically tigh**t*.

**Properties**

The above defined functions are very similar to real numbers. They also remind me a little of equivalence relations. Refer to Section 3.1 of *Introduction to Algorithms* 3rd Edition by Cormen et al. for a detailed list of properties of these functions including transitivity, reflexivity etc. along with their real number relational analogs.

xkcd/342

### Like this:

Like Loading...

*Related*