Class Code: AMC621 Instructor: Huilan Chang

1. An Intuitive Introduction to Order

See an example first: input size $=n$. Two algorithms Algo 1 and Algo 2 for the same problem.

• Suppose the every-case time complexities for Algo 1 and Algo 2 are $T_1(n)=100n$ and $T_2(n)=0.1n^2$, respectively.
• Algol will be more efficient if $100n<0.1n^2$, that is when $n>10000$.
• Algo 1 is called a linear-time algorithm; Algo 2 is called quadratic-time algorithm.

<aside>

🔹 Informal definition: $f(n)\in\Theta(n)$ if $f(n)$ is linear in $n$. $f(n)\in\Theta(n^2)$ if $f(n)$ is quadratic in $n$.

</aside>

$T_1(n)\in \Theta(n)$ and $T_2(n)\in \Theta(n^2)$. Algo 1 is more efficient than Algo 2 when $n$ is sufficiently large.

注意：文獻上通常用 “=”, 例如：$100n=\Theta(n)$ and $5n^2+100n+20=\Theta(n^2)$. 🔹 Some of the most common complexity categories: constant $k\in \mathbb{N}$. $\Theta(\lg n)$ logarithmic time, $\Theta(\log^k n)$ polylogarithmic time, $\Theta(n^{1/2})$ sub-linear time, $\Theta(n)$ linear time, $\Theta(n^k)$ polynomial time, $\Theta(n^2)$ quadratic time.

2. Rigorous Introduction to Order ($O, \Omega, \Theta, o$)

（板書上課, 內容不少，至少準備5 pages of A4)