# 1 How to measure the running speed of an algorithm?（如何衡量一个算法的运行速度？）

How to measure the running speed of an algorithm? What exactly does it mean for an algorithm to be fast or efficient well?

Of course, we cannot simply measure the “running time” of the algorithm, because the different computers have different configuration.

Maybe it runs slowly on this computer because this computer is 10 years old!

So you can’t say program A is slower than program B, just based on how long the computer is running the program. Because different computers are configured differently.

# 2 Asymptotic Notation（渐进分析）

Computer scientists and mathematicians developed the method of progressive analysis.

## 2.1 Big O notation (渐进上界 O 符号)

### 2.1.1 definition

A function f(x) runs on the order of G(x) if there exists some x value x_0 and some constant C for which f(x) is less than or equal to that constant times G(x) for all x greater than x_0. Then we say that f(x)=O(g(x)).

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \leq C \times g(x).

for example:

### 2.1.2 example

for another example（另一个例子）:
f(x) = 4x^2 + 16x + 2,
g(x) = x^4,
then, we have:
f(x) = O(g(x)),
that means: 4x^2 + 16x + 2 \leq C \times x^4.

when C=1（当 C 为 1 的时候）:

x 4x^2 + 16x + 2 < x^4 T or F
0 2 < 0 F
1 22 < 1 F
2 50 < 16 F
3 86 < 81 F
4 130 < 256 T
f(x) < g(x) T

## 2.2 Big Ω notation (渐进下界 Ω 符号)

### 2.2.1 definition

(1) f(x) \in g(x),
(2) there exists x_0, C,
(3) for all x greater x_0, f(x) \geq C \times g(x).

### 2.2.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = Ω(g(x)),
that means: 4x^2 + 16x + 2 \geq C \times x^2,

when C=1（当 C 为 1 的时候）:

x 4x^2 + 16x + 2 > x^2 T or F
f(x) > g(x) T

## 2.3 Big θ notation (渐进紧界 θ 符号)

### 2.3.1. definition

f(x) = \theta(g(x)) iff（当且仅当if and only if）
(1)f(x)=O(g(x)),
(2)f(x)=\Omega(g(x)),

f(x)=Ω(g(x))f(x)=O(g(x))，则f(x) = \theta(g(x))

### 2.3.2 example

f(x) = 4x^2 + 16x + 2,
g(x) = x^2,
then, we have:
f(x) = \theta(g(x)),
than means:f(x) = O(g(x)) and f(x) = \Omega(g(x)).

#### prove f(x) = O(g(x))

when C=5, x>=20:
4x^2 + 16x + 2 \leq 5 \times x^2
so,f(x) = O(g(x))

#### prove f(x) = Ω(g(x))

when C=1, x>=0:
4x^2 + 16x + 2 \geq x^2
so,f(x) = Ω(g(x))

you can see this pic：

0