FIND-MINIMUM $(A,n)$The FIND-MINIMUM algorithm reflects on the state of present day computer technology:
1 if $n=0$
2 then return NIL /* No minimum in an empty array. */
3 $m$ $\leftarrow $ $A[1]$
4 $i$ $\leftarrow $ $2$
5 while $i\le n$
6 do if $A[i]<m$
7 then $m$ $\leftarrow $ $A[i]$
8 $i$ $\leftarrow $ $i+1$
9 return $m$
$\begin{array}{c}{c}_{1}+{c}_{2}(n-1)+{c}_{3}\hfill \\ ={c}_{1}+{c}_{2}n-{c}_{2}+{c}_{3}\hfill \\ \text{Let}{c}_{4}={c}_{1}-{c}_{2}+{c}_{3}\text{}\hfill \\ ={c}_{4}+{c}_{2}n\hfill \end{array}$ |
Value of $n$ | ${n}^{3}$ | ${n}^{2}$ | ${n}^{1}$ | $4$ |
1 | 1 | 1 | 1 | 4 |
10 | 1000 | 100 | 10 | 4 |
100 | 1000000 | 10000 | 100 | 4 |
1000 | 1000000000 | 1000000 | 1000 | 4 |
INSERTION-SORT( $A$) | Cost | Times |
1 for $j$ $\leftarrow $ $2$ to $\mathrm{length}[A]$ | ${c}_{1}$ | $n$ |
2 do $\mathrm{key}$ $\leftarrow $ $A[j]$ | ${c}_{2}$ | $n-1$ |
3 $i$ $\leftarrow $ $j-1$ | ${c}_{3}$ | $n-1$ |
4 while $i>0$ and $A[i]>\mathrm{key}$ | ${c}_{4}$ | ${\Sigma}_{j=2}^{n}{t}_{j}$ |
5 do $A[i+1]$ $\leftarrow $ $A[i]$ | ${c}_{5}$ | ${\Sigma}_{j=2}^{n}({t}_{j}-1)$ |
6 $i$ $\leftarrow $ $i-1$ | ${c}_{6}$ | ${\Sigma}_{j=2}^{n}({t}_{j}-1)$ |
7 $A[i+1]$ $\leftarrow $ $\mathrm{key}$ | ${c}_{7}$ | $n-1$ |
$\sum _{j=2}^{n}j=\frac{n(n+1)}{2}-1$ |
$T(n)=(\frac{{c}_{4}}{2}+\frac{{c}_{5}}{2}+\frac{{c}_{6}}{2}){n}^{2}+({c}_{1}+{c}_{2}+{c}_{3}+\frac{{c}_{4}}{2}-\frac{{c}_{5}}{2}-\frac{{c}_{6}}{2}+{c}_{7})n-({c}_{2}+{c}_{3}+{c}_{4}+{c}_{7})$ |
$T(n)=\{\begin{array}{cc}c\hfill & \mathrm{if}n=1\hfill \\ 2T\left(\frac{n}{2}\right)+\Theta (n)\hfill & \mathrm{if}n1\hfill \end{array}$ |