Data Structures and Algorithm Analysis Notes 中的文章
• [Lecture 1] Introduction, Mathematics Review, Recursion
• [Lecture 2] Asymptotic Notation, Algorithm Analysis
• 本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

# [Lecture 2] Asymptotic Notation, Algorithm Analysis

## 1. Asymptotic Notation

### 1.1 Definitions

Here are some definitions to demonstrate the value trend of a function when the input N grows up .

The big-O notation $O$ defines a class of functions that have the same attribution :

$T\left(N\right)=O\left(f\left(N\right)\right)$ if there are positive constants $c$ and ${n}_{0}$ such that $T\left(N\right)\le cf\left(N\right)$ when $N\ge {n}_{0}$.

Note that 「$=$」 here is not a tradition symbol 「equal」, which describes $T\left(N\right)$ belongs to a set of functions satisfied with the requirement above.

Big-O notation

$O\left(f\left(N\right)\right)$ guarantees the function $T\left(N\right)$ has upper bound in the long run. We will not mind what the constant items $c$ and ${n}_{0}$ would be when $N$ becomes a huge number, that’s a fundamental idea about the term 「asymptotic」, $T\left(N\right)$ will be under some restriction of $f\left(N\right)$ in the end, when we say some function is of $O\left(f\left(N\right)\right)$, we guarantee the growth rate of this function will not be greater than $f\left(N\right)$.

Almost the same thing happens with the big-omega notation $\mathrm{\Omega }$ :

$T\left(N\right)=\mathrm{\Omega }\left(f\left(N\right)\right)$ if there are positive constants $c$ and ${n}_{0}$ such that $T\left(N\right)\ge cf\left(N\right)$ when $N\ge {n}_{0}$

Big-Omega Notation

To make it more exactly, there is big-theta notation $\mathrm{\Theta }$ to control the upper bound and lower bound :

$T\left(N\right)=\mathrm{\Theta }\left(f\left(N\right)\right)$ if and only if $T\left(N\right)=O\left(f\left(N\right)\right)$ and $T\left(N\right)=\mathrm{\Omega }\left(f\left(N\right)\right)$

And there is little-o notation describing the strict relation case, in which $T\left(N\right)$ is not in the set of $\mathrm{\Theta }\left(f\left(N\right)\right)$ :

$T\left(N\right)=o\left(f\left(N\right)\right)$ if $T\left(N\right)=O\left(f\left(N\right)\right)$ and $T\left(N\right)\ne \mathrm{\Theta }\left(N\right)$

As we will see those notations in our future, they are efficient tools to compare the relative growth rate of functions. Thus we will introduce some important rules firstly.

### 1.2 Rules of Asymptotic Notations

Rule 1

Supposing that

${T}_{1}\left(N\right)=O\left(f\left(N\right)\right),{T}_{2}\left(N\right)=O\left(g\left(N\right)\right)$

we have :

${T}_{1}\left(N\right)+{T}_{2}\left(N\right)=O\left(f\left(N\right)\right)+O\left(g\left(N\right)\right)=O\left(max\left(f\left(N\right),g\left(N\right)\right)\right)$

${T}_{1}\left(N\right)\cdot {T}_{2}\left(N\right)=O\left(f\left(N\right)\cdot g\left(N\right)\right)$

Rule 2

If $T\left(N\right)$ is a polynomial of degree $k$, then $T\left(N\right)=\mathrm{\Theta }\left({N}^{k}\right)$

Rule 3

${\mathrm{log}}^{k}N=O\left(N\right)$, for any constant $k$, that means the logarithmic functions grow more slowly than any polynomial functions

And we can make a list of functions in the order of growth rate :

Function Name
$c$ Constant
$\mathrm{log}N$ Logarithmic
${\mathrm{log}}^{2}N$ Log-squared
$N$ Linear
$N\mathrm{log}N$
${N}^{2}$ Quadratic
${N}^{3}$ Cubic
${2}^{N}$ Exponential

This list can be helpful to get intuitive impression. Besides we can compare the growth rate of two functions in a more general way by computing the limit :

$\underset{N\to \mathrm{\infty }}{lim}\frac{f\left(N\right)}{g\left(N\right)}$

The value of the limit shows the relationship of two functions :

• The limit is $0$ : $f\left(N\right)=o\left(g\left(N\right)\right)$
• The limit is $c\ne 0$ : $f\left(N\right)=\mathrm{\Theta }\left(g\left(N\right)\right)$
• The limit is $\mathrm{\infty }$ : $g\left(N\right)=o\left(f\left(N\right)\right)$
• No limit : No relationship of two functions

Here’s a brief example, supposing we have $f\left(N\right)=N\mathrm{log}N$ and $g\left(N\right)={N}^{1.5}$ :

$\underset{N\to \mathrm{\infty }}{lim}\frac{f\left(N\right)}{g\left(N\right)}=\underset{N\to \mathrm{\infty }}{lim}\frac{N\mathrm{log}N}{{N}^{1.5}}$

Using L’Hôpital’s rule, we have :

$\underset{N\to \mathrm{\infty }}{lim}\frac{f\left(N\right)}{g\left(N\right)}=\underset{N\to \mathrm{\infty }}{lim}\frac{\mathrm{log}N+cons{t}_{1}}{1.5{N}^{0.5}}$

According to Rule 1 :

$\underset{N\to \mathrm{\infty }}{lim}\frac{f\left(N\right)}{g\left(N\right)}=\underset{N\to \mathrm{\infty }}{lim}\frac{\mathrm{log}N}{1.5{N}^{0.5}}+\underset{N\to \mathrm{\infty }}{lim}\frac{cons{t}_{1}}{{N}^{0.5}}$

Using L’Hôpital’s rule again :

$\underset{N\to \mathrm{\infty }}{lim}\frac{f\left(N\right)}{g\left(N\right)}=\underset{N\to \mathrm{\infty }}{lim}\frac{cons{t}_{2}}{{N}^{0.5}}+\underset{N\to \mathrm{\infty }}{lim}\frac{cons{t}_{1}}{{N}^{0.5}}$

$\underset{N\to \mathrm{\infty }}{lim}\frac{f\left(N\right)}{g\left(N\right)}=0+0=0$

In fact this is another example to show $\mathrm{log}N$ is slower than any power function ${N}^{a}$ when $a$ is positive.

## 2. Algorithm Analysis

### 2.1 Model and Running Time

Take a piece of code, and we would like to know how well it would performance, the typical idea is to measure the running time. However there are lots of factors that will have effects on time, such as compiler options, the clock frequency of this machine you use, etc. We want our program analysis to be independent with those non-program factors.

In order to realise independence, we use a model assuming the basic operations, such as addition, multiplication, comparison, and assignment run for a time unit. Though we know exactly loading data from memory is much slower than executing addition in CPU. In addition we also assume our memory is infinity.

Since the input scale can be changeable, we will use ${T}_{worst}$ in worst-case to guarantee the upper bound of running time, and ${T}_{avg}$ in average-case to represent typical behaviour.

( Note that ${T}_{avg}$ sometimes would be really hard to analysis, in other case, the definition about average will have affect on ${T}_{avg}$. )

Now we will introduce the methods for algorithm analysis thought a simple problem.