Algorithms Notes – Chapter 2

References used for this section: A

Asymptotic Analysis

\Theta – notation

Definition\Theta (g(n)) = \{ f(n) : there exist positive constants c_{1},c_{2} and n_{0} such that 0 \le c_{1}g(n) \leq f(n) \leq c_{2}g(n) for all n \ge n_{0} \}.

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

\mathcal{O} – notation

Definition: \mathcal{O} (g(n)) = \{ f(n): there exist positive constants c and n_{0} such that 0 \le f(n) \le cg(n) for all n \ge n_{0} \}.

We abuse the notation for \mathcal{O} (g(n)) the same way as we do for \Theta (g(n)) (refer to the note above).

Since \Theta notation is a stronger notion than \mathcal{O} notation, it is evident that f(n) = \Theta (g(n)) implies f(n) = \mathcal{O} (g(n)). In other words, \mathcal{O}(g(n)) \subseteq \Theta(g(n)).

\Omega – notation

Definition: \Omega(g(n) = \{f(n): there exist positive constants c and n_{0} such that 0 \le cg(n) \le f(n) for all n \ge n_{0}\}.

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

Theorem: For any two functions f(n) and g(n), we have f(n) = \Theta(g(n)) if and only if f(n) = \mathcal{O}(g(n)) and f(n) = \Omega(g(n)).

This figure kind of summaries the above three notations:

big_theta

o – notation

Definition: o(g(n)) = \{f(n): for any positive constant c > 0 there exists a constant n_{0} > 0 such that 0 \le f(n) < cg(n) for all n \ge n_{0}\}.

This is very similar to \mathcal{O} notation. This example illustrates a key difference:

2n^2 = \mathcal{O}(n^2) and 2n = \mathcal{O}(n^2) however, 2n = o(n^2) but 2n^2 \not= o(n^2). In other words, we use o notation for upper bounds that are not asymptotically tight.

\omega – notation

Definition: w(g(n)) = \{f(n): for any positive constant c > 0 there exists a constant n_{0} > 0 such that 0 \le cg(n) < f(n) for all n \ge n_{0}\}.

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

\frac{n^2}{2} = \Omega(n) and \frac{n^2}{2} = \Omega(n^2). However, \frac{n^2}{2} = \omega(n) but \frac{n^2}{2} \not= \omega(n^2).  In other words, we use \omega notation for lower bounds that are not asymptotically tight.

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.

1337_part_2

xkcd/342

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s