CS 383, Algorithms
Time efficiency of an algorithm
An algorithm, you'll recall, is a well-defined computational procedure
for solving a particular computational task
A computational task is defined by describing
what inputs are to be provided,
and what outputs are desired for those inputs
The algorithm specifies the sequence of basic steps to be
carried out in order to address the given computational task
We'll see that what algorithms are used greatly impacts
the performance of programs based on those algorithms
Efficiency of computational procedures
Some programs are faster than others
Part of this is due to programming details
Most is due to differences in the underlying computational procedures
(algorithms)
Example: computing n choose k
we discussed a recursive approach based on a recurrence equation
(n, k) = (n-1, k-1) + (n-1, k)
other techniques exist too, like dynamic programming (to be discussed later in the course)
In class I ran a program that compares these two techniques
for small values of n, k, little time difference between them
for larger values (e.g., n=32, k=15), this changes drastically
Parenthetical remark: measuring CPU time
You can use the <ctime> library in g++ under Unix
clock() function returns current time in microseconds
practical resolution is of the order of 10 microseconds
Quantifying the speed of a computational procedure
We could measure speed as running time (secs)
Difficulties:
depends on particular values of input parameters
depends on hardware used, programing language, etc.
Reduce first problem by measuring time as a function of input size:
T(n) = secs required for input of size n
Doesn't eliminate dependence on inputs altogether
there could be several inputs of the same "size"
(e.g., for n choose k, if size is defined as n)
More importantly, this doesn't eliminate "platform dependence"
There's a related, practical, consideration
T(n) might be very hard to predict exactly
Efficiency in terms of the number of basic computational steps
It may be more feasible to count how many "basic steps"
are required by a given computational procedure
Recall the towers of Hanoi algorithm:
solve(n, source, target, spare):
solve(n-1, source, spare, target);
moveTopDisk(source, target);
solve(n-1, spare, target, source);
The basic step here is moving one disk
In this case, it is possible to figure out exactly how many steps
are used by the above procedure in solving the size n problem
as an explicit function NumSteps(n)
However, for other procedures an exact count may not be easily found
Approximating the running time
It is common practice to describe running times by *bounding*
the number of basic steps T(n) required for inputs of size n
We may be able to show that T(n) is at most a certain number,
or to show that T(n) is at least a certain number
Example: the insertion sort algorithm
The computational task here is sorting an array
input: an array a[1..n] containing objects from a totally ordered set
output: a permuted version of the array a[1..n] with a[i]<=a[j] for i<j
procedure: for i = 2 to n {
current = a[i]
j = i-1
while (j>0) and (a[j] > current) {
a[j+1] = a[j]
j = j-1
}
a[j+1] = current
}
We discussed how insertion sort works on the array
{8, 2, 5, 3}
How fast is insertion sort?
We'll need to count "basic steps" for arrays of length n
The number of steps isn't always the same
e.g. for a sorted array like {1, 2, 3, 4},
insertion sort is faster than for an unsorted array
We'll try to figure out "best case" and "worst case" scenarios
Worst case running time of insertion sort
Worst case (maximum time) analysis provides an upper bound on T(n)
For insertion sort, the outer loop requires n-1 passes
The inner loop requires *at most* i-1 passes
total steps for inner loop at most 2*(i-1)
Total steps for outer loop is a sum over i=2...n of
3 + 2*(i-1)
Do the sum; total is
3*(n-1) + n*(n-1)
This is an upper bound
What is the *best-case* time complexity of insertion sort?
the for loop requires n-1 steps, no matter what
the best case occurs when a[i] is already >= a[i-1] (no passes)
actually, the loop test in the while requires at least 1 step
the assignments/test in the for loop require a total of 4 steps
conclusion: best-case complexity (running time) is 4(n-1)
Who cares about algorithm efficiency?
You should, especially if your programs will handle large instances
Sorting example (we looked at n choose k earlier)
Compare insertion sort against quicksort, a more sophisticated algorithm
(times below are in seconds on a really old machine)
n insertion quicksort
sort
1000 0.03 0
2000 0.11 .01
3000 0.24 "
4000 0.43 "
5000 0.67 "
6000 1.01 "
7000 1.36 .02
8000 1.8 .01
9000 2.32 .02
10000 2.9 .02
20000 12.22 .05
30000 27.45 .07
40000 .12
50000 .13
60000 .16
70000 .20
80000 .23
90000 .25
100000 ? .29
Observations
Not only is quicksort much faster than insertion sort,
its running time increases more slowly too
Can you estimate the running time for insertion sort
on an instance of size 100000 (question mark in table)?
Answer: since for insertion sort one expects t(n) = C n^2,
t(100000) should be about 10^2 times as much as t(10000),
so t(100000) should be about 300 seconds (5 minutes)
What about quicksort?
Answer: this is harder since we haven't analyzed quicksort yet;
it turns out that t(n) = C n log n for quicksort (*average* case),
so one would expect t(10^5)/t(10^4) = 10 * (5/4) = 12.5,
which implies t(10^5) = 12.5 * t(10^4) = 12.5 * .02 = .25
(which is pretty close to the actual empirical result above)
How about t(10^6)?
Answer:
for insertion sort, t(10^6) = (approx.) 10^2 * t(10^5) = 8 hours
for quicksort, t(10^6) = (approx.) 10 * (6/5) * t(10^5) = 3.5 seconds
Conclusion
The *rate* of growth of t(n) is critical
Cn^2 is eventually (for large n) much slower than Dn log n
The values of the constants (C, D) often don't matter as much
so, for example, even though it's not really true that all
elementary operations take the same amount of time,
that assumption still allows good efficiency estimates;
***besides, exact values depend on the platform***
Rates of growth; big O notation
So far, I've shown you algorithms of different efficiencies
I've argued by example that the rate of growth of t(n) is
more important than the precise values of constants involved
But... what exactly *is* the rate of growth?
Big-O, threshold version
Given two functions t: N -> R+U{0} and f: N -> R+,
one writes t(n) = O(f(n)) and says "t(n) is of the order of f(n)" or "t(n) is big-O of f(n)"
if and only if the following occurs:
there is some (finite) constant C > 0 and some threshold n_0
so that
t(n) <= C*f(n) for all n >= n_0.
Properties of big-O
1) t(n) = O(t(n)) no matter what function t you consider
This is something that *ought* to happen, of course
The point here is that the above definition makes it happen
argument: take C=1 and n_0=0
since obviously t(n) <= 1*t(n) for all n>=0, we're done
2) t(n) = O(K*t(n)) for any value of K > 0
argument: take C=1/K and n_0=0
3) Threshold rule (no-threshold version of big-O)
Assume that f(n) > 0 for all values of n. Then:
t(n) = O(f(n)) if and only if there is a finite constant C
so that t(n) <= C*f(n) for all n (not just n>=n_0)
4) Maximum rule: (t1+t2)(n) = O(max(t1(n),t2(n)))
(it's also true that if t1(n) = O(f(n)) and t2(n) = O(g(n)),
then (t1+t2)(n) = O(f(n) + g(n)) )
Examples of big-O notation:
insertion sort satisfies t(n) = O(n^2) in the worst case
the towers of Hanoi function solve(n) has t(n) = O(2^n)
linear search for a target element in an array of length n
satisfies t(n) = O(n)
Analysis example: Euclid's gcd algorithm
The greatest common divisor of two positive integers m, n is:
gcd(m,n) = largest integer that divides both m and n evenly
Assuming n >= m, the naive algorithm that checks all possible divisors
from n down to 1 takes time O(n)
Side remark: Cn is linear in the magnitude of the number n,
but it's *exponential* in the *size* of the instance,
since the usual coding of n requires log n digits
Faster algorithm:
function Euclid(m, n) {
while (m > 0) {
temp <- m
m <- n mod m
n <- temp
}
return n
}
Outline of running time analysis:
t(n) = t(while) + t(return) = t(while) + 1
for each pass through the while body:
temp <- m: 1 step
m <- n mod m: 2 steps
n <- temp: 1 step
total of 4 steps per pass
for each while loop guard test:
1 step
=> t(n) = 1 + 1 + (# while passes)*(5)
Main target now:
determine an upper bound on the number of while passes
*Assume m <= n*
First approximation: get a loose upper bound
Since m <- n mod m on each pass, and since n mod m < m by definition,
it's clear that m decreases by at least 1 on each pass
Therefore, #passes <= m <= n
Conclusion so far:
Euclid satisfies t(n) <= 2 + 5*n
In particular, t(n) = O(n) (choose C=7, n_0=1 in the definition)
Tightening the bound
In fact, the number of while passes is much less than m in the worst case
Claim: n mod m is at most n/2
Argument:
if m <= n/2, that's obvious since mod-ing by m returns values < m
if m > n/2, then n div m is at least 1, so less than n/2 remains
Therefore, the larger of m and n is halved or better on each pass
This implies that the number of passes is at most log_2(n) + 1
Conclusion:
Euclid satisfies t(n) <= 2 + 5*(1 + log_2(n))
In particular, t(n) = O(log n) (what values of C and n_0?)
Trouble in Big-O land?
We've found big-O running times for several algorithms
For Euclid's gcd algorithm in particular, we found *two* different big-O results (for the *same* algorithm):
1. t(n) = O(n)
2. t(n) = O(log n)
Which one is "right"?
They both are - it's just that big-O notation only captures upper bounds:
1. says that t(n) is "no worse than" C*n
2. says that t(n) is no worse than D*log(n)
Big Omega notation does lower bounds
Given two functions t: N -> R+U{0} and f: N -> R+,
one writes t(n) = Omega(f(n)) and says "t(n) is big-Omega of f(n)", if and only if the following occurs:
There is some (finite) constant D > 0 and some threshold n_0 so that t(n) >= D*f(n) for all n >= n_0.
Properties of big-Omega
1) t(n) = Omega(t(n)) no matter what function t you consider
Argument: take D=1 and n_0=1
Since obviously t(n) <= 1*t(n) for all n>=1, we're done
2) t(n) = Omega(K*t(n)) for any value of K > 0
Argument: take D=1/K and n_0=1
3) If t1(n) = Omega(f(n)) and t2(n) = Omega(g(n)),
then (t1+t2)(n) = Omega(f(n) + g(n))
Example: the worst-case time complexity of Euclid's gcd algorithm satisfies t(n) = Omega(log n)
Argument: consider the instance m=f_{k-1}, n=f_k, where the f_i's are consecutive Fibonacci numbers
Notice that since n = f_{k-1} + f_{k-2} = m + f_{k-2} and since f_{k-2} < f_{k-1} = m,
the remainder n mod m is just f_{k-2}.
Therefore, the resulting execution proceeds as follows:
m n
f_{k-1} f_k = f_{k-1} + f_{k-2}
f_{k-2} f_{k-1} = f_{k-2} + f_{k-3}
f_{k-3} f_{k-2} = f_{k-3} + f_{k-4}
. .
. .
. .
0 1
The total number of rows in this table is k.
Constructing each row takes a constant number of steps.
The running time for this instance is therefore C*k.
Since f_k is exponential in k, we have k =(approx.) D*log(n),
so the running time for this instance is C'* log(n).
This proves that t(n) = Omega(log n) as claimed.
Big-Theta notation
If an algorithm satisfies both t(n) = O(f(n)) and t(n) = Omega(f(n)) for the same function f,
then one says that the algorithm runs in time Theta(f(n)).
Example: Euclid's gcd algorithm Euclid(m,n) runs in time Theta(log n)
(assuming that m and n are of similar sizes here)
Given two functions t: N -> R+U{0} and f: N -> R+,
one writes t(n) = Theta(f(n)) and says "t(n) is big-Theta of f(n)", if and only if the following occurs:
t(n) is both big-O(f(n)) and big-Omega(f(n))
Equivalently:
There are (finite) constants C, D > 0 and a threshold n_0 so that D*f(n) <= t(n) <= C*f(n) for all n >= n_0.
Properties of big-Theta
1) t(n) = Theta(t(n)) no matter what function t you consider
2) t(n) = Theta(K*t(n)) for any value of K > 0
3) If t1(n) = Theta(f(n)) and t2(n) = Theta(g(n)), then (t1+t2)(n) = Theta(f(n) + g(n))