[Home Page - Algorithms](/@roger61205/Algorithms) [Home Page - Theorey of Computation](/@roger61205/Theory-of-Computation) [Home Page - Data Structures](/@roger61205/Data-Structures) [toc] # Notes ## Asymptotic Notations ### Notations #### O-Notation $$ O(g(n))=\{f(n)|\exists\ positive\ constants\ c\ and\ n_0:0\leq f(n)\leq cg(n)\forall\ n\geq n_0\} $$ ![](https://i.imgur.com/ddQXqO8.png) If $f(n)\in O(g(n))$, we write $f(n)=O(g(n))$ * $g(n)$: An asymptotic upper bound for $f(n)$. #### Ω-Notation $\Omega(g(n))=\{f(n)|\exists\ positive\ constants\ c\ and\ n_0:0\leq cg(n)\leq f(n)\forall\ n\geq n_0\}$ ![](https://i.imgur.com/ntKHPcB.png) If $f(n)\in O(g(n))$, we write $f(n)=O(g(n))$ * $g(n)$: An asymptotic lower bound for $f(n)$. #### Θ-Notation $$ \Theta(g(n))=\{f(n)|\exists\ positive\ constants\ c_1,c_2\ and\ n_0:0\leq c_1g(n)\leq f(n)\leq c_2g(n)\forall\ n\geq n_0\} $$ ![](https://i.imgur.com/ECXoiuX.png) If $f(n)\in O(g(n))$, we write $f(n)=O(g(n))$ * $g(n)$: An asymptotic tight bound for $f(n)$. :::info By Stirling's approximation, $n!=\sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))\\\Rightarrow log(n!)=\Theta(nlogn)$ ::: #### o-Notation $$ o(g(n))=\{f(n),\forall\ constants\ c>0,\exists\ a\ constant\ n_0>0:0\leq f(n)<cg(n)\forall n\geq n_0\} $$ In another view, $$ lim_{0\to\infty}\frac{f(n)}{g(n)}=0 $$ #### ω-Notation $$ \omega(g(n))=\{f(n),\forall\ constants\ c>0,\exists\ a\ constant\ n_0>0:0\leq cg(n)<f(n)\forall n\geq n_0\} $$ In another view, $$ lim_{0\to\infty}\frac{f(n)}{g(n)}=\infty $$ ### Properties and Theorems #### Transivity $\begin{cases}f(n)=\Theta(g(n))\land g(n)=\Theta(h(n))\Rightarrow f(n)=\Theta(h(n))\\f(n)=O(g(n))\land g(n)=O(h(n))\Rightarrow f(n)=O(h(n))\\f(n)=\Omega(g(n))\land g(n)=\Omega(h(n))\Rightarrow f(n)=\Omega(h(n))\\f(n)=o(g(n))\land g(n)=o(h(n))\Rightarrow f(n)=o(h(n))\\f(n)=\omega(g(n))\land g(n)=\omega(h(n))\Rightarrow f(n)=\omega(h(n))\end{cases}$ #### Reflexivity $\begin{cases}f(n)=\Theta(f(n))\\f(n)=O(f(n))\\f(n)=\Omega(f(n))\end{cases}$ #### Symmetry $f(n)=\Theta(g(n))$ if and only if $g(n)=\Theta(f(n))$ #### Transpose Symmetry 1. $f(n)=O(g(n))$ if and only if $g(n)=\Omega(f(n))$ 2. $f(n)=o(g(n))$ if and only if $g(n)=\omega(f(n))$ #### Comparisons 1. $f(n)$ is asymptotically smaller than $g(n)$ if $f(n)=o(g(n))$ 2. $f(n)$ is asymptotically larger than $g(n)$ if $f(n)=\omega(g(n))$ ## Time Complexity Analysis ### Analysis of Nonrecurisive Algorithms :::info ![](https://i.imgur.com/1UUFeUF.png) $$ T(n)=c_1n + c_2(n–1)+c_4(n–1)+c_5\sum_{j=2}^nt_j+c_6\sum_{j=2}^n(t_j-1)+c_7\sum_{j=2}^n(t_j-1)+c_8(n–1) $$ 1. For $t_j=1,j=2,3,...,n$ $$ \begin{aligned} T(n)=&c_1n+c_2(n–1)+c_4(n–1)+c_5(n–1)+c_8(n–1)=(c_1+c_2+c_4+c_5+c_8)n\\ &–(c_2+c_4+c_5+c_8) \end{aligned} $$ 2. For $t_j=j,j=2,3,...,n$ $$ \begin{aligned} T(n)=&c_1n+c_2(n–1)+c_4(n–1)+c_5(\frac{n(n-1)}{2}-1)+c_6(\frac{n(n-1)}{2})+c_7(\frac{n(n-1)}{2})\\ &+c_8(n–1)\\ =&\frac{c_5+c_6+c_7}{2}n^2–(c_1+c_2+c_4+(\frac{c_5-c_6-c_7}{2})+c_8)n–(c_2+c_4+c_5+c_8) \end{aligned} $$ ::: Therunningtimeof an algorithm on aparticular input is the number of primitive operations or steps executed. ### Analysis of Recurisive Algorithms #### Assumption The boundary conditions are usually expressed as $$ T(n)=O(1) $$ for sufficiently smaill $n$. #### Methods 1. Recurrence Trees Method :::info For $T(n)=3T(\lfloor\frac{n}{4}\rfloor)+\Theta(n^2)$ ![](https://i.imgur.com/25xbh1V.png) ![](https://i.imgur.com/01BvY6h.png) $$ \begin{aligned} T(n)&=cn^2+\frac{3}{16}cn^2+(\frac{3}{16})^2+...+(\frac{3}{16})^{log_4n-1}cn^2+\Theta(n^{log_43})\\ &=\sum_{i=0}^{log_4(n-1)}(\frac{3}{16})^icn^2+\Theta(n^{log_43})\\ &<\sum_{i=0}^\infty(\frac{3}{16})^icn^2+\Theta(n^{log_43})\\ &=\frac{1}{1-\frac{3}{16}}cn^2+\Theta(n^{log_43})\\ &=\frac{16}{13}cn^2+\Theta(n^{log_43})\\ &=O(n^2) \end{aligned} $$ ::: 2. Substitution Method :::info For $T(n)=\begin{cases}1,n=1\\2T(\frac{n}{2})+n,n>1\end{cases}$ 1. Guess the solution Guess $T(n)=nlogn+n$ 2. Induction 1. Base Step For $n=1$, $T(1)=nlogn+n=1=T(n)$ 2. Induction Step Let $T(k)=klogk+k$. $\begin{aligned}&\begin{aligned}T(k)&=2T(\frac{k}{2})+k\\&=2(\frac{k}{2}log\frac{k}{2}+\frac{k}{2})+k\\&=klog(\frac{k}{2})+k+k\\&=k(logk-log2)+k+k\\&=klogk+k\\\end{aligned}\\&\Rightarrow T(n)=\Theta(nlogn)\end{aligned}$ ::: 3. Master Method It is used for many divide-and-conquer recurrences of the form $T(n)=aT(\frac{n}{b})+f(n), a\geq1,b>1,f(n)>0$ Compare $n^{log_ba}$ and $f(n)$ 1. Case 1: $f(n)=O(n^{log_b(a)-\epsilon})$ for some constant $\epsilon>0$ $T(n)=\Theta(n^{log_ba})$ 2. Case 2: $f(n)=\Theta(n^{log_ba}log^kn), k\geq0$ $T(n)=\Theta(n^{log_ba}log_2^{k+1}n)$ 3. Case 3: $f(n)=\Omega(n^{log_b(a)+\epsilon})$ for some constant $\epsilon>0$ and $f(n)$ satisfies the regularity condition $af(\frac{n}{b})\leq cf(n)$ for some constant $c<1$ and all sufficiently large $n$. $T(n)=\Theta(f(n))$ ## Time Measurement ### C #### `time.h` 1. Variables and Functions 1. Types 1. `clock_t`: A type suitable for storing the processor time 2. `time_t`: A type suitable for storing the calendar time 2. Macros * `CLOCKS_PER_SEC` It represents the number of processor clocks per second. 3. Functions 1. `clock()` It returns the processor clock time used since the beginning of an implementation defined era (normally the beginning of the program). ```c clock_t clock(void); ``` :::info ```c clock_t start, stop; start = clock(); stop = clock(); runTime= (double)(stop - start) / CLOCLS_PER_SEC; ``` ::: 2. `time()` It calculates the current calender time and encodes it into `time_t` format. ```c time_t time(time_t *timer); ``` 2. Accuracy :::info ![image](https://hackmd.io/_uploads/SyjJkZpFp.png) ::: In a computer, two adjacent processes has a specific interval called tick. For a function that can obtain time, it actually gain the point that a tick starts. Therefore, if a function that takes a tiny period smaller than a tick, than the accuray is extremely low. 3. Ways to Calculating Time 1. Bad Way :::info ```c int counter = 0; clock_t start, stop; do { counter++; start = clock(); function(); stop = clock(); elapsedTime += stop-start; }while(elapsedTime < 1000); double = elapsedTime / counter; ``` ::: 2. Accurate Way :::info ```c clock_t start = clock(); int counter = 0; do { counter++; function(); }while(clock() - start < 1000) double elapsedTime=(double)(clock() - start) / CLOCKS_PER_SEC; double runTime=elaspedTime / counter; ``` ::: # Exercises ## Introduction to Algorithms (Third Edition), T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein ### P.108 Exercise 4.3.1 Show that the solution of $T(n)=T(n-1)+n$ is $O(n^2)$. Guess $T(n)\leq cn^2$, $$ \begin{aligned} T(n)&\leq c(n-1)^2+n\\ &=cn^2-2cn+c+n\\ &=cn^2+n(1-2c)+c\\ &\leq cn^2,c>\frac{1}{2} \end{aligned} $$ Therefore $T(n)=O(n^2)$ ### P.108 Exercise 4.3.2 Show that the solution of $T(n)=T(\lceil n/2\rceil)+1$ is $O(\log_2n)$. Guess $T(n)\leq c\log_2(n-a)$ $$ \begin{aligned} T(n)&\leq c\log_2(\lceil n/2\rceil-a)+1\\ &\leq c\log_2((n+1)/2-a)+1\\ &=c\log_2((n+1-2a)/2)+1\\ &=c\log_2(n+1-2a)-c\log_22+1,c\geq1\\ &\leq c\log_2(n+1-2a)\\ &\leq c\log_2(n-a) \end{aligned} $$ There $T(n)=O(\log_2n)$. ### P.108 Exercise 4.3.3 Show that the solution of the recurrence $T(n)=2T(\lfloor n/2\rfloor)+n$ is $\Omega(n\log_2n)$ Guess that $T(n)\geq c(n+a)\log_2(n+2)$, $$ \begin{aligned} T(n)&\geq 2c(\lfloor n/2\rfloor+a)(\log_2((n-1)/2+a))+n\\ &geq 2c((n-1)/2+a)(\log_2((n-1)/2+a))+n\\ &=2c\frac{n-1+2a}{2}\log_2\frac{n-1+2a}{2}+n\\ &=c(n-1+2a)\log_2(n-1+2a)-c(n-1+2a)\log_22+n\\ &=c(n-1+2a)\log_2(n-1+2a)+(1-c)n-(2a-1)c,0\leq c<1,n\geq\frac{c(2a-1)}{1-c}\\ &\geq c(n-1+2a)\log_2(n-1+2a)\\ &\geq c(n+a)\log_2(n+a) \end{aligned} $$ There $T(n)=\Omega(n\log_2n)$. ### P.114 Exercise 4.4.3 Use arecursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=4T(n/2+2)+n$. $$ \begin{aligned} T(n)&=c\sum_{i=0}^{\lg n-1}(2^in+2\cdot4^i)+\Theta(n^2)\\ &=c\sum_{i=0}^{\lg n-1}2^in+\sum_{i=0}^{\lg n-1}2\cdot4^i+\Theta(n^2)\\ &=c(\frac{2^{\lg n}-1}{2-1}n+2\cdot\frac{4^{\lg n}-1}{4-1})+\Theta(n^2)\\ &=c((2^{\lg n}-1)n+\frac{2}{3}(4^{\lg n}-1))+\Theta(n^2)\\ &=c((n-1)n+\frac{2}{3}(n^2-1))+\Theta(n^2)\\ &=\Theta(n^2) \end{aligned} $$ **References** NCKUCSIE 1112_F721300 Algorithms NCKUCSIE 1101_F720300_1 Data Structure Introduction to Algorithms (Third Edition), T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein NCKUCSIE 1121_F732001 Theory of Computation An Introduction to Formal Languages and Automata, 7th Edition (6th Edition) by Peter Linz (UC Davis) Introduction to Automata Theory, Languages and Computation, 3rd Edition by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman [C Library - <time.h> - Tutorialspoint](https://www.tutorialspoint.com/c_standard_library/time_h.htm) Fundamentals of Data Structures in C 2nd Edition by Ellis Horowitz