2. Algorithm Analysis

Once an algorithm is shown to be correct, consider the:

Efficiency in time and space
- Big O
- Big Omega
- Big Theta
Complexity in terms of the size of the input
Worse, average, and best case
- Focus on the worst case
Asymptotic analysis: $\lim_{n\rightarrow \infty}{time(n)}$

Complexity

The time taken will depend on the instance of the problem being solved.

RAM Model of Computation

Abstract random access machine

Accessing any byte in memory takes constant time
Basic operations (arithmetic, comparison, assignment) take one unit of time
Time inside loops proportional to the number of iterations
Subroutine time is the time to execute its body

Formal Definitions

Big O (upper bound)

O(G) = {f|\exists c>0: \exists x_0: \forall x\ge x_0: 0 \le f(x) \le c \cdot g(x)}

That is, $f(x)$ is part of the set $O(g)$ if there exists a positive multiplier $c$ such that for every value of $x$ greater than $x_0$ , $f(x) \le c\cdot g(x)$ .

Big Omega (lower bound)

\Omega(G) = {f \exists c>0: \exists x_0: \forall x\ge x_0: 0 \le c\ cdot g(x) \le f(x)}

That is, $f(x)$ is part of the set $\Omega(g)$ if there exists a positive multiplier $c$ such that for every value of $x$ greater than $x_0$ , $c\cdot g(x) \le f(x)$ .

Big Theta (tight bound)

\Omega(g) = O(g) \cap \Omega(g)

That is, $f(x)$ is part of the set $\Theta(g)$ if it is such that for every value of $x$ above $x_0$ , there exists $c_1$ and $c_2$ such that that $c_1 \cdot g(x) \le f(x) \le c_2 \cdot g(x)$ .

The worst case and best case are functions: the algorithm is not, so we cannot define the algorithm by Big O/Omega/Theta notation.

The best case of an algorithm will be $\Theta(g)$ ; the algorithm is not $\Theta(g)$ . Ideally, an algorithm would be separately categorized by its best and worst case. In practice, we often categorize the algorithm by its worst case.

Common functions, sorted by complexity descending:

Functions
$x!$
$a^x$
$x^a$
$x \log(x)$
$x$
$\log(x)$
$a$