DATA STRUCTURES AND
ALGORITHM
CHAPTER TWO
ALGORITHM ANALYSIS
INTRODUCTION
• How do you compare two algorithms for solving some
problem in terms of efficiency?
• We could implement both algorithms as computer programs
and then run them on a suitable range of inputs, measuring
how much of the resources in question each program uses.
• This approach is often unsatisfactory for four reasons.
Cont..
• First, there is the effort involved in programming and testing
• Second, there is always the chance that one of the programs
was “better written” than the other.
• Third, the choice of empirical test cases might unfairly favor
one algorithm.
• Fourth, how would you know if any of the algorithms can
meet the resource budget?
Cont..
• These problems can often be avoided by using asymptotic
analysis.
• Asymptotic analysis measures the efficiency of an algorithm,
or its implementation as a program, as the input size
becomes large.
• Asymptotic analysis has proved useful to computer scientists
who must determine if a particular algorithm is worth
considering for implementation.
Cont..
• The critical resource for a program is most often its running
time.
• However, you cannot pay attention to running time alone.
• You must also be concerned with other factors such as the
space required to run the program (both main memory and
disk space).
• Typically, you will analyze the time required for an
algorithm, and the space required for a data structure.
Cont..
• Many factors affect the running time of a program.
• Some relate to the environment in which the program is
compiled and run. Like the speed of the computer’s CPU, bus,
and peripheral hardware.
• The programming language and the quality of code
generated by a particular compiler can have a significant
effect.
• The “coding efficiency” of the programmer who converts the
algorithm to a program can have a incredible impact as well.
Cont..
• One of the primary consideration when estimating an
algorithm’s performance is the number of basic operations
required by the algorithm to process an input of a certain
size.
• The terms “basic operations” and “size” are both rather
unclear and depend on the algorithm being analyzed.
• Size is often the number of inputs processed.
• A basic operation must have the property that its time to
complete does not depend on the particular values of its
operands.
EXAMPLE: SELECTION PROBLEM
• Given a list of N numbers, determine the kth largest, where k
N.
• Algorithm 1:
(1) Read N numbers into an array
(2) Sort the array in decreasing order by some simple algorithm
(3) Return the element in position k
Cont..
EXAMPLE: SELECTION PROBLEM…
• Algorithm 2:
(1) Read the first k elements into an array and sort them in decreasing
order
(2) Each remaining element is read one by one
• If smaller than the kth element, then it is ignored
• Otherwise, it is placed in its correct spot in the array, bumping one
element out of the array.
(3) The element in the kth position is returned as the answer.
Cont..
EXAMPLE: SELECTION PROBLEM…
• Which algorithm is better when
• N =100 and k = 100?
• N =100 and k = 1?
• What happens when N = 1,000,000 and k =
500,000?
• There exist better algorithms
ALGORITHM ANALYSIS
• We only analyze correct algorithms
• An algorithm is correct
• If, for every input instance, it stops with the correct output
• Incorrect algorithms
• Might not stops at all on some input instances
• Might halt with other than the desired answer
• Analyzing an algorithm
• Is Predicting the resources that the algorithm requires
• Resources include
• Memory
• Communication bandwidth
• Computational time (usually most important)
Cont..
ALGORITHM ANALYSIS…
• Factors affecting the running time
• computer
• compiler
• algorithm used
• input to the algorithm
• The content of the input affects the running time
• typically, the input size (number of items in the input)
is the main consideration
• E.g. sorting problem the number of items to be
sorted
• E.g. multiply two matrices together the total
number of elements in the two matrices
• Machine model assumed
• Instructions are executed one after another, with no
concurrent operations Not parallel computers
RUNNING-TIME OF ALGORITHMS
• Boundaries are for the algorithms, rather than programs
• programs are just implementations of an algorithm, and
almost always the details of the program do not affect the
bounds
• Boundaries are for algorithms, rather than problems
• A problem can be solved with several algorithms, some
are more efficient than others
Other Example of Analyses of
Algorithm
Example 2: Consider a simple algorithm to solve the problem
of finding the largest value in an array of n integers.
• The algorithm looks at each integer in turn, saving the
position of the largest value seen so far.
• This algorithm is called the largest-value sequential
search and is shown by the following function:
Cont..
int largest(int A[], int n) {
int currlarge = 0;
for (int i=1; i<n; i++)
if (A[currlarge] < A[i])
return currlarge;
}
Cont..
• The growth rate for an algorithm is the rate at which the
cost of the algorithm grows as the size of its input
grows.
• A growth rate of cn is often referred to as a linear growth
rate or running time.
• This means that as the value of n grows, the running
time of the algorithm grows in the same proportion.
Cont..
• Doubling the value of n roughly doubles the running time.
• An algorithm whose running-time equation has a highest-
order term containing a factor of n2 is said to have a
quadratic growth rate.
For example, 2n2 represents a quadratic growth rate and 2n
represents an exponential growth rate.
• This name comes from the fact that n appears in the
exponent. The equation n! is also growing exponentially.
Cont..
Cont..
Cont..
Cont..
Cont..
Cont..
BEST /WORST / AVERAGE/ CASE
• Best-case running time
• sort a set of numbers in increasing order; and the data is
already in increasing order
• Worst-case running time of an algorithm
• The longest running time for any input of size n
• An upper bound on the running time for any input
guarantee that the algorithm will never take longer
• Example: Sort a set of numbers in increasing order; and
the data is in decreasing order
• The worst case can occur fairly often
• E.g. in searching a database for a particular piece of
information
• Average-case running time
• May be difficult to define what “average” means
Cont..
BEST, WORST, AND AVERAGE CASES
• For some algorithms, different inputs of a given size require
different amounts of time.
• For example, consider the problem of searching an array
containing n integers to find the one with a particular value K
(assume that K appears exactly once in the array).
• The sequential search algorithm begins at the first position in
the array and looks at each value in turn until K is found. Once K
is found, the algorithm stops.
Cont..
BEST, WORST, AND AVERAGE CASES
• There is a wide range of possible running times for the
sequential search algorithm.
• The first integer in the array could have value K, and so only
one integer is examined.
• In this case the running time is short. This is the best case
for this algorithm, because it is not possible for sequential
search to look at less than one value.
Cont..
BEST, WORST, AND AVERAGE CASES
• Alternatively, if the last position in the array contains K, then
the running time is relatively long, because the algorithm
must examine n values.
• This is the worst case for this algorithm, because sequential
search never looks at more than n values.
Cont..
BEST, WORST, AND AVERAGE CASES
• If we implement sequential search as a program and run it
many times on many different arrays of size n, or search for
many different values of K within the same array, we expect
the algorithm on average to go halfway through the array
before finding the value we seek.
• On average, the algorithm examines about n/2 values. We
call this the average case for this algorithm.
Cont..
BEST, WORST, AND AVERAGE CASES
• When analyzing an algorithm, should we study the best,
worst, or average case?
• Normally we are not interested in the best case, because this
might happen only rarely and generally is too optimistic for a
fair characterization of the algorithm’s running time.
• In other words, analysis based on the best case is not likely
to be representative of the behavior of the algorithm.
Cont..
BEST, WORST, AND AVERAGE CASES
• How about the worst case?
• The advantage to analyzing the worst case is that you know for certain
that the algorithm must perform at least that well.
• This is especially important for real-time applications, such as for the
computers that monitor an air traffic control system.
• Here, it would not be acceptable to use an algorithm that can handle n
airplanes quickly enough most of the time, but which fails to perform
quickly enough when all n airplanes are coming from the same direction.
ASYMPTOTIC ANALYSIS
Asymptotic Analysis is the big
idea that handles above
issues in analyzing
algorithms. In Asymptotic
Analysis, we evaluate the
performance of an algorithm in
terms of input size (we don't
measure the actual running
time). We calculate, how the
Cont..
ASYMPTOTIC ANALYSIS
• Asymptotic analysis refers to the study of an algorithm as the
input size “gets big” or reaches a limit (in the calculus sense).
• However, it has showed to be so useful to ignore all
constant influences that asymptotic analysis is used for
most algorithm comparisons.
• Asymptotic analysis is a form of “back of the envelope”
estimation for algorithm resource consumption.
READING ASSIGNMENT
ANALYSIS OF ALGORITHMS (QUALITATIVE
AND QUANTITATIVE ANALYSIS)
End of Chapter
Two
any ?,
comment?
