Introduction to Algorithms/Introduction

Video Link

The theoretical study of computer program performance and resource usage.

What’s more importance than performace? Why study algs and perf?

Problem: Sorting

Insertion-Sort

Input sequence: $<a_{1},a_{2},\dots,a_{n}>$ of numbers output sequence: permutation of them, s.t. $a_{1}’ \leqslant a_{2}’ \leqslant \dots \leqslant a_{n}$

Insertion-Sort(A,n) //Sorts A[1,...,n]
  for j <- 2 to n
    do key <- A[j]
       i <- j - 1
  while i > 0 and A[i] > key
    do A[i + 1] <- A[i]
       i <- i - 1
       A[i + 1] <- key

• Running time
  • Depends on input sequence
  • Depends on input size
  • Upper bounds

Kinds of analysis

Worst-case (usually)

• $T(n)$ = max time on any input size of $n$

Average-case (sometimes)

• $T(n)$ = expected time over all input of size $n$

  Need assumption of the statistical distribution

Best-case (bogus)

What’s ins-sort’s worst time?

• relative speed (on same machine)
• absolute speed (on diff machine)

IDEA: Asymptotic analysis

1. ignore mechine dependent constants
2. look at the growth of $T(n)$ as $n \to \inf$

Asymptotic notation

• $\Theta$ - notation: Drop low order terms and ignore leading constants.

Worst case of insertion sort: inverse sorted:

\[T(n)=\sum_{j=2}^{n}\Theta(j)=\Theta(n^2)\]

Merge Sort

1. if $n=1$, done
2. Recursively sort $A[1,\dots,\left[ \frac{n}{2} \right] ]$ and $A\left[ \left[ \frac{n}{2} \right] +1 ,\dots,n\right]$
3. Merge 2 sorted lists ($\Theta(n)$)

\[T(n)=\Theta(n)+2T\left( \frac{n}{2} \right), \quad n>1\]

graph TD
A((cn)) --> B(("T(n/2)"))
A--> C(("T(n/2)"))