Week 02


Efficiency


Program Properties2/46

Recall that we want our programs to be:

Guaranteeing correctness requires Testing increases confidence that program may be correct ...


... Program Properties3/46

Trade-off:   efficiency  vs  clarity

[Diagram:Pics/misc/knuth-small.jpg]

"Premature optimization is the root of all evil" ... Don Knuth

"KnuthAtOpenContentAlliance" by Flickr user Jacob Appelbaum, uploaded to en.wikipedia by users BeSherman, Duozmo - Flickr.com (via en.wikipedia). Licensed under CC BY-SA 2.5 via Wikimedia Commons


Program/Algorithm Efficiency4/46

How to determine efficiency?

Measure program execution costs   (experimental)

Analyse algorithm execution costs   (theoretical)


... Program/Algorithm Efficiency5/46

Example: finding max value in an unsorted array

int findMax(int a[], int N) {
   int i, max = a[0];
   for (i = 1; i < N; i++)
      if (a[i] > max) max = a[i];
   return max;
}

Core operation? ... compare a[i] to max

How many times? ... clearly N-1

Execution cost grows linearly   (i.e. 2 × #elements ⇒ 2 × time)


... Program/Algorithm Efficiency6/46

Example: finding max value in a sorted (ascending) array

int findMax(int a[], int N) {
   return a[N-1];
}

No iteration needed; max is always last.

Execution cost is constant   (same regardless of #elements)


... Program/Algorithm Efficiency7/46

Example: finding given value k in an array

int search(int k, int a[], int N) {
   int i;
   for (i = 0; i < N; i++)
      if (a[i] == k) return i;
   return -1;
}

Core operation? ... compare a[i] to k

How many times? ... not so straightforward

Need to consider best/worst/average-case costs.


... Program/Algorithm Efficiency8/46

Best case:   find k in a[0]   (1)

Worst case:   no k or find k in a[N-1]   (N)

Average case:   find k "in the middle" of a   (N/2)

Could devise "overall average" if we know likelihood of each case.

If not, take pessimistic view ... worst case.

In fact, both worst and average cases grow linearly.


Algorithmic Complexity9/46

Cost is primarily interesting for large data

Leads to complexity classes and big-O notation

Definition:   g(n) ∈ O(f(n))   if g(n) ≤ c.f(n)   ∀ n > N0

Complexity classes


... Algorithmic Complexity10/46

Algorithms are "rated" by their complexity class.

Thus we might say "quicksort has worst case complexity O(n2) "

Assigning an algorithm to a complexity class ...


Want to know everything ... try the Big-O Cheat Sheet


Exercise 1: Assigning Complexity Class11/46

Give complexity classes for above functions:

What about?