-----------------------------------------------------------------------------
WEEK 13 LECTURE NOTES
CS108, FALL 2007
-----------------------------------------------------------------------------
ANNOUNCEMENTS:
* "Announcements" for this week will be listed on the class website's
"Important Announcements" link, not on this "Lecture Notes" page.
-----------------------------------------------------------------------------
INTRO TO ALGORITHM ANALYSIS
===========================
THE MAX1 ALGORITHM
------------------
Consider N integer values, represented by the variables
a[1], a[2], a[3], ..., a[N]. (We can use subscripts, or array notation,
to represent the N different values.)
An "algorithm" is a procedure, or series of steps, which does
a task or solves a problem.
Here is an algorithm, we can call it "MAX1", which computes
the maximum value (largest value) among the N integer values:
Step 1: set b[1] = max( a[1], a[2] )
Step 2: set b[2] = max( b[1], a[3] )
Step 3: set b[3] = max( b[2], a[4] )
Step 4: set b[4] = max( b[3], a[5] )
...etc...
Step N-1: set b[N-1] = max( b[N-2], a[N] )
The value b[N-1] now contains the largest of all the N inputted values.
This is the value we wanted.
(Note: the max(x,y) function above, is defined as the larger of x and y,
e.g.: max(3,5) = 5, and max(8,3) = 8, and max(10,10) = 10.)
Notice that, if we are given N integer values, it takes us N-1 "steps"
to find the largest value among those N integers.
In other words, for an input of "size N", our algorithm performs "N-1 steps".
We can now define a function f(n), which specifies the number of steps
performed by our algorithm when it is given an input of size n:
f(n) = n-1
f(n) is called the "running time function" or "time complexity function"
for our MAX1 algorithm.
Notice that it's called a "running time" function, even though it tells us the
number of "steps" performed, not the "amount of time" it took to perform them.
Researchers use that terminology, because time and number of steps are related:
the more steps you perform, the more time it'll take.
THE SEARCH1 ALGORITHM
---------------------
Consider N integer values, represented by the variables
a[1], a[2], a[3], ..., a[N]. (Again, we can use subscripts or array notation
to represent the N different values.)
Here is an algorithm, we can call it "SEARCH1", which outputs
the array index of some "target" value being searched for.
For example, if the number of integers is N=4, and if those 4 integers are
a[1]=10, a[2]=30, a[3]=25, a[4]=17, and if we decide to search for the
target value k=25, then our algorithm should output
the location 3. (If the target value, often called a "key" value,
is not contained in our data set, then our algorithm should output -1.
Actually, this is very similar to what is done by some of Java's built-in
search-related commands.)
Here is the complete SEARCH1 algorithm:
Step 1: if a[1]=k, then output 1, and STOP immediately.
Step 2: if a[2]=k, then output 2, and STOP immediately.
Step 3: if a[3]=k, then output 3, and STOP immediately.
Step 4: if a[4]=k, then output 4, and STOP immediately.
...etc...
Step N: if a[N]=k, then output N, and STOP immediately.
Step N+1: output -1
Notice there's something different about SEARCH1. Even though the size
of the problem is always N (i.e., N data values are always inputted),
the number of steps performed might be anywhere from 1 to N+1, depending on
when the "STOP immediately" command is reached.
For example, consider our previous situation:
N=4, and a[1]=10, a[2]=30, a[3]=25, a[4]=17.
If we are searching for k=10, then we'll only do 1 step before stopping.
If k=17, then we'll do 4 steps before stopping.
If k=1000000, then we'll do 5 steps before stopping.
If k=25, then we'll do 3 steps before stopping.
As you can see, for an input of size N, SEARCH1 might make us do only 1 step,
or maybe N steps, or maybe N+1 steps, or anything inbetween.
Therefore, for SOME data values and SOME target values, SEARCH1's running time
function is: f(n) = 1 step.
For a different set of data values and/or target values, its running time
function is: f(n) = n+1 steps.
And for a different set, its running time function is: f(n) = 3 steps,
or anything between 1 step and n+1 steps.
Therefore, SEARCH1 has many running time functions!
It would be hard to write them all. So, we need some shortcut way
to say "SEARCH1's running time function will vary, but we know that it
will be at least 1 step, and at most n+1 steps."
We can use the "Greek notation" (discussed in the next section, below)
to do this.
SIDENOTE:
You might be wondering if it's "legal" to call it "Step 1" in situations
when Step 1 contains multiple steps. E.g., MAX1's "Step 1" computes
the larger of two values, which actually requires us to do a couple of steps.
Also, SEARCH1's "Step 1" contains approximately three steps.
It turns out that all of this is OK, in algorithm analysis.
Because, it turns out that the mathematical definitions of the
Greek notations ("orders" of growth) discussed below, are independent
of constants. So, whether "Step 1" performs one step, or whether it
performs a constant multiple of one step (e.g., 3 steps, or 10 steps),
we are still allowed to call it "Step 1."
The only requirement in algorithm analysis, is that "Step 1"
(and the other "Steps") is "reasonably defined". An *unreasonable* Step 1
would be something like:
"Compute the average of infinity values," i.e. something which
performs an exponential number of steps (defined in the sections below)
in one unit of time.
SIDENOTE:
Of course, if you are interested in *very accurately* estimating how long
it will take your algorithm or program to run, then you will want to define
and count your steps very accurately and in detail. However, for determining
general "orders" of running times, as is done with the Greek notation,
then extreme accuracy isn't needed, because any constant-multiple difference
in your definition of "one step" will be mathematically eliminated
(by the mathematical definitions of the Greek notation).
Although that may sound as if "orders" will only give you running-time results
that are too general and approximate to be of any use, they actually do group
algorithms into useful categories that really do give you a good idea
about the speed of an algorithm and the speed of competing algorithms.
We'll see this in the next couple of sections below,
when we "compare" algorithms.
ORDERS OF FUNCTIONS
-------------------
We can classify functions by their "orders of growth", or "orders."
(Below, "x^y" will be shorthand for "x raised to the power y",
because plaintext files (such as this this one) can't display superscripts.)
A function f(n) = n-1 is said to be of "order n".
A function f(n) = n is said to be of "order n".
A function f(n) = n+1 is said to be of "order n".
A function f(n) = 3*n + 10 is said to be of "order n".
A function f(n) = n^2 is said to be of "order n^2" ("order n squared").
A function f(n) = n^2 + 100 is said to be of "order n^2".
A function f(n) = 3*n^2 + 1 is said to be of "order n^2".
A function f(n) = 4*n^2 - 3*n + 50 is said to be of "order n^2".
Notice that the "order" of a simple function can be easily computed
by just looking at the term with the largest power of n, and then
ignoring the constant in front of that term.
Note: a "constant function" is said to be of "order 1":
f(n) = 10 is "order 1".
f(n) = 10000 is "order 1".
Mathematically, the "order" of a function represents
the growth rate of that function when n is extremely large.
Functions with the same "order", grow at the same rate:
* As n approaches infinity, functions of the "same order"
only differ by a constant multiple.
* As n approaches infinity, functions of "different orders"
differ by a nearly-infinite amount.
Example:
The function f(n) = n^2 always has "smaller" values
of f(n) as compared to the function f(n) = 1000*n^2 + 100*n + 10000.
But, if you were to actually plot the two graphs, then as n becomes extremely
large (approaching infinity), the two graphs actually would start to get
"closer" together, because they are of the same order.
(In particular, when n=1, the second function's value is 11,100, and the
first function's value is 1, meaning that the second function's value
is 11,100 times larger than the first function's value.
But, when n is very large, e.g. n=infinity, then the second function's value is
only 1000 times the first function's value, proving that the two graphs
get "closer" (relatively speaking!). To compute this fact yourself, you will
need to use "limit" mathematics, usually discussed in calculus courses.)
ORDERS OF ALGORITHMS
--------------------
Algorithms are classified according to the "orders"
of their running time functions.
E.g., MAX1's running time function is f(n)=n-1, which is
"order n", and therefore MAX1 is said to be an "order n" algorithm.
We can compare algorithms, by comparing their orders.
If you have to choose either an "order n^2" algorithm for finding the
maximum value among n data values, or an "order n" algorithm like MAX1,
then you can safely choose the one with the lower order, because it will
perform fewer steps and will therefore run faster (especially when
the size of the problem, n, is large). Because, as was said above,
two running times f(n) and g(n) of different orders will differ
by a nearly-infinite amount when n is extremely large.
(Of course, if you are presented with two "order n" algorithms for finding
the largest of a bunch of data values, and are asked to choose an algorithm,
then you will have to ask for more specifics about their
running time functions and how accurately those running time functions
defined a "Step".)
TABLE OF ORDERS
---------------
As shown in the previous section, it's useful to know how two orders
compare to each other, e.g. when choosing an algorithm.
In practice, many real-world problems also have running times
that include a logarithmic term. Some well-known sorting algorithms
have running times like f(n) = n * log(n).
Here is a "Table" showing common "orders", and their relationships:
("Larger" orders are higher up, "smaller" orders are lower down)
...etc...
---- order "n!" i.e., n factorial
....etc...
---- order 2^n
...etc...
...etc...
---- order n^4 * log(n)
---- order n^4
---- order n^3 * log(n)
---- order n^3
---- order n^2 * log(n)
---- order n^2
---- order n * log(n)
---- order n
---- order log(n)
---- order 1
Memorize this Table, because it will be useful on the exams.
GREEK-LETTER NOTATION
---------------------
The "Greek letter" notation is a handy way of specifying and comparing
"orders" of functions, such as running time functions.
WARNING:
ASCII TEXT FILES (LIKE THIS ONE) DO NOT ALLOW GREEK AND MATHEMATICAL
NOTATION, SO I WILL USE "[element of]" TO REPRESENT THE MATHEMATICAL
SYMBOL FOR "element of a set", WHICH RESEMBLES A ROUNDED LETTER "E".
ALSO, GREEK LETTER SYMBOLS WILL BE REPLACED BY THEIR NAMES, SUCH AS "THETA".
(IF YOU ARE NOT FAMILIAR WITH MATH NOTATION OR GREEK LETTERS,
THEN YOU CAN LOOK AT THESE SYMBOLS IN YOUR TEXTBOOK OR A MATH BOOK.)
Note:
* Greek letter notation is not fully standardized in the
field of algorithm analysis. E.g., some researchers use "BIG OH"
instead of "THETA". Below, we'll use the most common definitions.
* Also, some researchers and books use "=" instead of "[element of]",
even though "=" is not mathematically accurate.
THETA NOTATION
--------------
Theta notation is used to specify the "order" of a function.
THETA (i.e., capital Greek letter theta) looks sort of like a
capital letter "O" -- but with a horizontal line through the middle.
The MAX1 algorithm's running time function was f(n)=n-1,
which we said earlier was of "order n". Therefore, we can write:
f(n) [element of] THETA(n)
meaning that MAX1's running time function f(n) is of "order n".
Since MAX1's running time function is "order n", then MAX1
is said to be an "order n algorithm."
f(n) [element of] THETA(n) is pronounced as:
"f is order n" or
"f is of order n" or
"f is in theta of n" or
"f is an element of theta of n" or etc.
Often, B(n) and W(n) are used to represent an algorithm's
"best-case running time" and "worst-case running time".
The SEARCH1 algorithm's "best-case" running time function was f(n)=1,
so we can write B(n)=1. B(n) is of order 1, so we write:
B(n) [element of] THETA(1).
The SEARCH1 algorithm's "worst-case" running time function was f(n)=n+1,
so we can write W(n)=n+1. W(n) is of order n, so we write:
W(n) [element of] THETA(n).
THE BASIC DEFINITION:
THETA is defined as the set of all functions of some specified order.
E.g., THETA( g(n) ) is the set of all functions that have
the same "order" as the function g(n).
Therefore, if f(n) is an element of the set THETA( g(n) ),
then f(n) has the same "order" as g(n).
THE TRUE, MATHEMATICAL DEFINITION:
Consider a function f(n) that is non-negative for all integers n>=0.
Then "f(n) [element of] THETA(g(n))" if there exists an integer n0 and
constants c1>0 and c2>0, such that for all integers n>=n0,
c1*g(n) =0.
Then "f(n) [element of] BIG-OH(g(n))" if there exists an integer n0 and
a constant c>0 such that for all integers n>=n0, f(n) =0.
Then "f(n) [element of] BIG-OMEGA(g(n))" if there exists an integer n0 and
a constant c>0 such that for all integers n>=n0, f(n)>=cg(n).
The SEARCH1 algorithm's "best-case" running time function was f(n)=1.
The SEARCH1 algorithm's "worst-case" running time function was f(n)=n+1.
Therefore, SEARCH1's running time function has an order that is
always order 1 or larger. We can therefore write:
f(n) [element of] BIG-OMEGA(1).
SMALL-OH NOTATION
-----------------
SMALL-OH (i.e., lower-case Greek letter omicron) looks like a
lowercase letter "o". It's pronounced "small oh" even though
it's really the Greek omicron.
f(n) [element of] SMALL-OH(n) is pronounced as:
"f is small oh of n" or
"f is in small oh of n" or
"f is an element of small oh of n" or etc.
THE BASIC DEFINITION:
SMALL-OH is defined as the set of all functions whose order is
strictly less than some specified order.
E.g., SMALL-OH( g(n) ) is the set of all functions that have
smaller "order" than the function g(n).
THE TRUE, MATHEMATICAL DEFINITION:
Consider a function f(n) that is non-negative for all integers n>=0.
Then "f(n) [element of] SMALL-OH(g(n))" if there exists an integer n0 and
a constant c>0 such that for all integers n>=n0, f(n) =0.
Then "f(n) [element of] SMALL-OMEGA(g(n))" if there exists an integer n0 and
a constant c>0 such that for all integers n>=n0, f(n) > cg(n).
The MAX1 algorithm's running time function was f(n)=n-1.
Therefore, f(n) [element of] SMALL-OMEGA( 1 ).
POLYNOMIAL AND EXPONENTIAL RUNNING TIMES
----------------------------------------
We'll continue here, next week.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
End Of File