Introduction

Algorithms

Asking

What's Algorithms?

The theoretical study of computer-program performance and resource usage.

What's more important than performance?

• modularity
• user-friendliness
• correctness
• programmer time
• maintainability simplicity
• functionality
• extensibility
• robustness
• reliability

Why study algorithms and performance?

• Performance often draws the line between what is feasible and what is impossible.
• Algorithmic mathematics provides a language for talking about program behavior.
• Performance is the currency of computing,it's the universal thing that you quantify.

---

Insertion sort

Input: sequence 〈a₁, a₂, ..., a_n 〉of numbers. Output: permutation〈a'₁, a'₂, ..., a'_n 〉such that a'₁ ≤ a'₂ ≤ ··· ≤ a'_n.

INSERTION-SORT(A,n)  ▷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

• The running time depends on the input.
• Parameterize the running time by the size of the input.
• Generally, we seek upper bounds on the running time(because everybody likes a guarantee).

Kinds of analyses

• Worst-case: (usually)
  • \(T(n)\) = maximum time of algorithm on any input of size n.
• Average-case: (sometimes)
  • \(T(n)\) = expected time of algorithm over all Inputs of size n.
  • Need assumption of statistical distribution of inputs.
• Best-case: (bogus)
  • Cheat with a slow algorithm that works fast on some input.

Asymptotic Analysis

HUGE IDEA: - Ignore machine-dependent constants. - Look at growth of T(n) as \(n \to \infty\).

\(\Theta\)-notation

• Drop low-order terms.
• Ignore leading constants.

Insertion sort analysis

• Worst case: Input reverse sorted

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

• Average case: All permutations equally likely

  \(T(n)=\sum_{j=2}^{n}\Theta(j/2)=\Theta(n^2)\quad[arithmetic series]\)

---

Merge sort

1. If n=1, done.
2. Recursively sort A[1.. \(\lceil n/2 \rceil\)] 1 and A[\(\lceil n/2+1 \rceil\).. n].
3. Merge the 2 sorted lists.

Key subroutine: MERGE

Analyzing merge sort

1. \(\Theta(1)\)

2. \(2T(n/2)\)¹

3. \(\Theta(n)\)

\[ T(n)=\begin{cases} \Theta(1) & n=1 \\ T(n/2)+\Theta(n) & n>1 \end{cases} \]

Recursion tree

---

1. Sloppiness: Should be \(T(\lceil n/2 \rceil)+T(\lfloor n/2 \rfloor)\)​, but it turns out not to matter asymptotically.↩︎