Runtime and Asymptotic Notation

In the previous lecture, we showed a naive way to analyze the runtime of algorithms. But this naive approach is very heavy and can be particularly troublesome when comparing algorithms that have complex runtime expressions. To simplify this, we introduce the asymptotic notation. A high-level intuition of the asymptotic notation is that it captures, and only captures the growth speed of functions.

The running time of every instance is sandwiched between the best case and the worst case running time. The worst case is often more important because:

it guarantees that the algorithm will never take longer time.
for some algorithms, the worst case is quite frequent.
often the average case is as bad as the base case.

Where the average case is defined as the performance on “average” input. e.g. for sorting it means that we assume that every possible permutation is equally likely.

Some key observations:

the biggest-order term (e.g. vs. ) dominates the runtime as grows.
and how the runtime scales with is more important than constant factors (for sufficiently large ).
additive smaller order terms become irrelevant for large .
we care about large because small problems are always easy to solve.

Asymptotic Notation:

Definition: Notation

For a given non-negative function we denote by the set of functions A function belongs to the set if it can be “sandwiched” between and for sufficiently large . By the convention of computer science literature, we write instead of . We say that is an asymptotically tight bound of .

Intuitively, means that captures grows essentially the same speed as .

Example

expresses tight upper and lower bounds on . There are other two notations:

Use if we only want to express an upper bound.
Use if we only want to express a lower bound.

The formal definition of these two new notations are similar:

Definition: Notation

For a given non-negative function we denote by the set of functions For a given non-negative function we denote by the set of functions

Tip

We also have and indicate strictly slower and faster growth, respectively:

An overview of asymptotic notation:

Notation	Meaning	Analogy
	grows at most as fast as
	grows at least as fast as
	grows as fast as
	grows slower than
	grows faster than

Caution

Always remember that is a “incorrect” convention for expressing .

By using the asymptotic notation, we can now describe the runtime of insertion sort as: ### Common runtimes

Mathematical expression	Name
	logarithmic time
	linear time
	quadratic time
	cubic time
for	polynomial time
	exponential time

Tip

Every polynomial of grows strictly slower than every polynomial of .
Every polynomial of grows strictly slower than every exponential function.

How to find

It is often helpful to divide by , e.g. Then try sandwiching the constant term.
Remember that .
Also remember that inequalities need to hold for all .
No need to invest time to find the best possible constants.

Practical rules to make runtime analysis simple

For two non-negative functions and :

Slower functions can be ignored:
Asymptotic times can be multiplied:

Asymptotic notation: comparing sets

Is true or false? (Tip: think of as a placeholder for an anonymous function from the set of all functions that grow linearly in .)

Such statement is true if no matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid.