Given a finite set of non-negative integers, find the smallest
non-negative integer not in the set.
How would you solve it?
How many different ways could you solve it?
Which solution is best?
What does it mean to be the best solution?
A Solution
Return the smallest non-negative integer not in a set.
int smallest(int s[])
for i = 0 to s.size()
found = false
for j = 0 to s.size() - 1
found = found || i == s[j]
if !found
return i
Another Solution
Return the smallest non-negative integer not in a set.
int smallest(int s[])
sort(s)
for i = 0 to s.size() - 1
if i != s[i]
return i
return s.size()
Yet Another Solution
Return the smallest non-negative integer not in a set.
int smallest(int s[])
found[s.size() + 1] = { false }
for i = 0 to s.size() - 1
if s[i] ≤ s.size()
found[s[i]] = true
for i = 0 to s.size()
if !found[i]
return i
Program Analysis
There are many programs, all different.
Which program can be judged suitable?
It depends on your criteria.
Memory use, speed, message count, ...
Start with execution time.
Performance is usually related to other criteria.
It takes time to use a resource.
Program performance can be measured or estimated.
Determining Performance
Measure execution time.
It’s a definitive measure.
But algorithms don’t execute; they’re not code.
It requires implementing the algorithm.
There are other problems too.
Problems
Measurements are context dependent.
Determining context accurately is difficult.
Comparing results is hard.
Contexts must match to be meaningful.
Meaningful measurements are hard.
Estimated Performance Analysis
If you don’t know, guess (or estimate).
Ignore the details, go for the big picture.
Estimating is simpler than measuring.
Skillful professionals estimate well.
Estimation is a skill to develop.
Estimation Advantages
Estimates are more comparable then are measurements.
The context is mostly ignored when estimating.
Estimates are more durable than are measurements.
Not as closely tied to hardware or software technology.
Modeling Algorithms
Model the algorithm by counting important parts of the algorithm.
The algorithm is reduced to a count, other details abstracted away.
Make sure you understand what’s being counted.
Sorting Example
Model a sorting algorithm by counting
the time it takes to sort n elements.
Or the number of comparisons done.
Or the number of elements moved.
Database Example
Model a distributed-database algorithm by counting
f(n) is the number of messages it takes to perform a
transaction.
Or the time it takes to commit a transaction.
Or the number of times a transaction is overtaken and aborted.
Asymptotic Estimates
Counting can be tedious and difficult to get right.
Rather than count, estimate the count.
There are many ways to estimate counts.
An upper bound on f(n)’s behavior is useful.
It represents potential worst-case behavior.
Other bounds are possible, but harder to find.
Upper-Bound Estimates
An upper bound of f(n)’s behavior is a
function g(n) with the property that
C*g(n) ≥f(n)
as n grows without bound for some positive constant C.
