Chapter 1 Analysis Basics
Prerequisites
You should
know how to:
·
Describe how to analyze an algorithm
·
Explain how to choose the operations that are
counted and why others are not
·
Explain how to do a best-case, worst-case, and
average-case analysis
·
Work with logarithms, probabilities, and summations
·
Describe Θ( f ), Ω( f ), O( f ), growth
rate, and algorithm order
·
Use a decision tree to determine a lower bound on
complexity
·
Convert a simple recurrence relation into its closed
form
§
Determine if they solve the problem
§
Determine how efficient they are in terms of time
and space
In class exercise:
In
teams, develop an algorithm (some code, not an entire program) for the
following problem. You have an array on integers (1000 of them) and each
integer is between 1 and 10. Count the number of 1’s, 2’s, etc.
TIME is important.
The more operations an algorithm does, the longer it takes to run. But
in analyzing algorithms the number of seconds (or microseconds) and algorithm
takes to run is not a good measure because it will be different from computer
to computer. We will develop ways of formulating mathematical equations that
express the complexity of an algorithm.
Two basic kinds of algorithms
· Repetitive
· Recursive
1.1 What is analysis?
Consider the two algorithms in your textbook. Each finds the largest of
four integers.
ALGORITHM # 1
largest = a
if b > largest then
largest
= b
end if
if c > largest then
largest
= c
end if
if d > largest then
largest
= d
end if
return largest
ALGORITHM # 2
if a > b then
if
a > c then
if
a > d then
return
a
else
return
d
end
if
else
if
c > d then
return
c
else
return
d
end
if
end
if
else
if
b > c then
if
b > d then
return
b
else
return
d
end
if
else
if
c > d then
return
c
else
return
d
end
if
end
if
end if
Which one is better? Why? Which one is faster? Which one takes up more
space?
Most of the time we will be dealing with algorithms that work on some
unknown number of inputs, say N. The question then becomes, can we determine a
formula for expressing how many operations in terms of N?
Consider the following two algorithms:
for i = 1 to N
a[i]
= a[i]*10
end for
for i = 1 to N
for
j = 1 to N
a[i,j]
= a[i,j]* 10
end
for
end for
How many multiplications does each one do?
Suppose
that one some algorithm, Algorithm A, does N+10 operations, and Algorithm B
does N+1000 operations. Is there any real difference?
1.1.1 Input Classes
Suppose that instead of
multiplications we are concerned with assignment statements. Here is a simple
algorithm to find the largest integer in an array of N integers.
for
i = 2 to N do
if list[i] > largest then
largest = list[i]
end if
end
for
If the largest integer happens to occur in position 1 in the array, how many assignment statements will be executed? What if it appears in position 5? How many different ways are there to place 10 distinct integers into an array? Does this suggest that the algorithm works differently on different “classes” of inputs? Hmm, this may be a problem because we cannot determine an exact formulation; there seems to be a best-case and a worst-case and many cases in between. This is another topic we will have to discuss concerning algorithms.
1.1.2 Space Complexity
Some algorithms need lots of
space to store temporary variables while others do not. In the beginning of
computer development space was very important. Even Bill Gates once said, “640K
ought to be enough for anybody.” However as memory got larger and cheaper, the
space problem decreases in importance. Many programmers today code applications
without much thought as to how big they are; they feel that consumers will just
purchase enough memory to handle the increased size of programs.
But times are changing again.
With the advent of PDA and embedded systems, space has become important again.
If you want a computer in your wrist-watch, there is only limited room
available. To write programs for such computers, the programmer must be aware
of the space those programs require!
Exercises:
In class we will discuss exercises 1, 2 and 3 on page 10 of your text. As a homework assignment, you are to do exercises 4 and 5.