# Analysis of Algorithms

Information on this page is taken from *The Algorithm Design Manual* by Steven
S. Skiena.

## RAM Model of Computation

Machine-independent algorithm design depends upon a hypothetical computer
called the **Random Access Machine** or **RAM**. Under this model of computation,
we are confronted with a computer where

- Each
*simple*operation (+, *, -, =, if, call) takes exactly one time step. - Loops and subroutines are the composition of many single-step operations.
- Each memory access takes exactly one time step. Further, we have as much memory as we need.

Under the RAM model, we measure run time by counting up the number of steps an algorithm takes on a given problem instance. We consider different time complexities that define a numerical function, representing time versus problem size.

**Worst-case complexity**of the algorithm is the function defined by the maximum number of steps taken in any instance of size \(n\).**Best-case complexity**of the algorithm is the function defined by the minimum number of steps taken in any instance of size \(n\).**Average-case complexity**of the algorithm is the function defined by the average number of steps taken in any instance of size \(n\).

## Big Oh Notation

**Big Oh** simplifies our analysis by ignoring levels of detail that do not
impact our comparison of algorithms. The formal definitions are as follows:

- \(f(n) = O(g(n))\) means \(c \cdot g(n)\) is an
*upper bound*on \(f(n)\). Thus there exists some constant \(c\) such that \(f(n)\) is always \(\leq c \cdot g(n)\), for large enough \(n\). - \(f(n) = \Omega(g(n))\) means \(c \cdot g(n)\) is an
*lower bound*on \(f(n)\). Thus there exists some constant \(c\) such that \(f(n)\) is always \(\geq c \cdot g(n)\), for large enough \(n\). - \(f(n) = \Theta(g(n))\) means \(c_1 \cdot g(n)\) is an upper bound on \(f(n)\) and \(c_2 \cdot g(n)\) is a lower bound on \(f(n)\). Thus there exists constants \(c_1\) and \(c_2\) such that \(f(n) \leq c_1 \cdot g(n)\) and \(f(n) \geq c_2 \cdot g(n)\).

For example, \(2n^2 + 100n + 6 = O(n^2)\), because I choose \(c = 3\) and \(3n^2 \geq 2n^2 + 100n + 6\) when \(n\) is big enough.

### Big Oh Classes

Big Oh groups functions into a set of classes, such that all the functions in a particular class are equivalent with respect to the Big Oh. A small variety of time complexities suffice and account for most algorithms that are widely used in practice.

Class Name | Function |
---|---|

Constant | \(f(n) = 1\) |

Logarithmic | \(f(n) = \log n\) |

Linear | \(f(n) = n\) |

Superlinear | \(f(n) = n lg n\) |

Quadratic | \(f(n) = n^2\) |

Cubic | \(f(n) = n^3\) |

Exponential | \(f(n) = c^n\) |

Factorial | \(f(n) = n!\) |

We say that a faster-growing function **dominates** a slower-growing
one. Specifically, when \(f\) and \(g\) belong to different classes (i.e. \(f(n)
\neq \Theta(g(n))\)), we say \(g\) dominates \(f\) when \(f(n) = O(g(n))\),
sometimes written \(g >> f\).

### Big Oh Operations

The sum of two functions is governed by the dominant one.

\begin{equation} O(f(n)) + O(g(n)) \rightarrow O(max(f(n), g(n))) \end{equation}Multiplying a function by a constant does not affect its asymptotic behavior.

\begin{equation} O(c \cdot f(n)) \rightarrow O(f(n)) \end{equation}When two functions in a product are increasing, both are important.

\begin{equation} O(f(n)) * O(g(n)) \rightarrow O(f(n) * g(n)) \end{equation}## Logarithms

A **logarithm** is simply an inverse exponential function. Saying \(b^x = y\) is
equivalent to saying that \(x = \log_b y\). Exponential functions grow at a
distressingly fast rate. Thus, inverse exponential functions -
i.e. logarithms - grow refreshingly slowly. Logarithms arise in any process
where things are repeatedly halved.

**Binary search** is a good example of an \(O(\log n)\) algorithm. If searching
for a particular name \(p\) in a telephone book, we start by comparing \(p\)
against the middle. Then we discard half the names. Only twenty comparisons
suffice to find any name in the million-name Manhattan phone book!

Logarithms appear in trees (height is \(\log_2 n\)), bits (\(\log_2 n\) bits required to store a number in binary).

### Logarithm Properties

The \(b\) term in \(\log_b y\) is the **base** of the logarithm. Three bases are of
importance for mathematical and historical reasons.

- Base \(b = 2\): The
**binary logarithm**, usually denoted \(lg n\), is a base 2 logarithm. Most algorithm applications of logarithms imply binary logarithms. - Base \(b = e\): The
**natural log**, usually denoted \(ln x\), is a base $e = 2.71828…$ logarithm. - Base \(b = 10\): Less common today is the base-10 or
**common logarithm**, usually denoted as \(\log x\).

It is easy to convert a logarithm from one base to another. This is a consequence of the formula:

\begin{equation} \log_a b = \frac{\log_c b}{\log_c a} \end{equation}Thus, changing the base of \(\log b\) from base-a to base-c simply involves dividing by \(\log_c a\).

The base of the logarithm has no real impact on the growth rate. We are usually justified in ignoring the base of the logarithm when analyzing algorithms.