Algorithm performance Analysis- operation count method

Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 1 of Science for Women
1. The Algorithm:
An algorithm is a finite set of instructions that if followed accomplish particular
task. In addition, every algorithm must satisfy the following criteria:
1- Inputs: there are zero or more inputs which are externally supplied.
2- Outputs: At least one output is produced.
3- Definiteness: each instruction in algorithm must be clear and
unambiguous, example for clear instruction ( add 6 to x) and example for
ambiguous instruction (divide 5 on 0), i.e., all people must understand it
at the same the understanding and solve it at the same the solving.
4- Finiteness: If we trace out the instructions of an algorithm, then for all
cases the algorithm will terminate after la finite number of steps.
5- Effectiveness: every instruction must be sufficiently basic that it can, in
principle, be carried out by a person using only pencil and paper. It is not
enough that each operation be definite as in (3), but it must also be
feasible.
We can distinguish between an algorithm and a program as follow:
Each algorithm must contain the previous five conditions and can be
described in many ways:
• A natural language such as English can be used but we must be very
careful that the resulting instructions are definite( condition 3) .
• Pseudo-code.
• Flow chart.
A program does not necessarily satisfy condition 4. One important
example of such a program for a computer is its operating system, which
never terminate ( except for system crashes) but continue in a wait loop
until more jobs are entered. We will deal strictly with programs that always
terminate.
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 2 of Science for Women
2. Types of Algorithms:
1. Off-line algorithms: all input in memory before time starts, want final
result.
2. On-line algorithms: input arrives at discrete time steps, intermediate
result furnished before next input.
3. Real-time: Elapsed time between two inputs (outputs) is a constant O(1).
We will mostly be concerned with off-line algorithms where all of the input is
known before the algorithm starts.
3.Performance Analysis and Measurement:
One goal is to develop a skills for making evaluative judgments about
programs. There are many criteria upon which we can judge a program, for
instance:
1. Does it do what we want it to do?
2. Does it work correctly according to the original specifications of the task?
3. Is there documentation that describes how to use it and how it works?
4. Are procedures created in such a way that the perform logical subfunctions?
The above criteria are all important when it comes to writing software,
most especially for large systems. Though we will not be discussing how to
reach these goals, we will try to achieve them throughout this lectures with
the programs we write.
There are other criteria for judging program that have a more direct
relationship to performance. These have to do with their computing time
and storage requirements.
Performance evaluation can be loosely divided into two major phases:
(1) a priori estimates and (2) a posteriori testing. We refer to these as
performance analysis and performance measurement respectively.
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 3 of Science for Women
3.1. Performance Analysis of Algorithm:
Algorithm analysis is the determining of algorithm efficiency and then
enhancing it. There is two criterions directly relates to algorithm performance
that are:
3.1.1. Space Complexity:
The space complexity of a program is the amount of memory it needs to
run to completion. The space needed by each program is seen to be the sum
of the following components:
• A Fixed Part that is independent of the characteristics (e.g., number,
size) of the inputs and outputs. This part typically includes the instruction
space (i.e., space for the code), space for simple variables and fixed
size component variables (also called aggregate), space for constant,
etc.
• A Variable Part that consists of the space needed by component
variables whose size is dependent on the particular problem instance
being solved, space needed by referenced variables (to the extent that
this depends on instance characteristics), and the recursion stack space
( in so far as this space depends on the instance characteristics).
The space requirement S(p) of any program p may therefore be written
as:
S(p) = c + Sp ( Instance Characteristics) where c is constant.
3.1.2.Time Complexity:
The time complexity of a program is the amount of computer time it
needs to run to completion. The time, T(p), taken by a program p, is the sum
of the compile time and the run (or execution ) time. The compile time does
not depend on the instance characteristics. Also, we may assume that a
compiled program will be run several times without recompilation.
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 4 of Science for Women
Consequently, we shall concern ourselves with just the run time of the
program. The run time is defined by tp (Instance Characteristics). The time
requirement T(p) of any program p may therefore be written as:
T(p) = c + tp (Instance Characteristics) where c is the compilation time.
Two manageable approaches to estimating run time are (1) identify one
or more key operations and determine the number of times these are
performed and (2) determine the total number of steps executed by the
program.
3.1.2.1. Operations Count Method:
One way to estimate the time complexity of a program or function is to
select one or more operations, such as add, multiply, and compare, and to
determine how many of each is done. The success of this method depends on
our ability to identify the operations that contribute most to the time complexity.
Several examples of this method as follow.
Example (1): Write a function that return the position of the largest element in
the array a[1..n], and then estimate its time complexity using operations count
method.
Solution:
Function Max(var a:ElemList; n:integer): integer;
Var pos:integer;
Begin
Pos:=1;
For i:=2 to n do
If ( a[pos] < a[i] ) then
Pos:= i;
Max:=pos;
End
We can estimate its time complexity by the number of comparisons
made between elements of the array a. each iteration of the for loop makes
one such comparisons, so the total number of element comparisons is n-1.
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 5 of Science for Women
The function Max does other comparisons (each iteration of the for loop is
preceded by a comparison between i and n) that are not included in the
estimate. Other operation such as initializing pos and incrementing the for loop
index i are also not included in the estimate. If we included these other
operations into our count , the count will increase by a constant factor.
Example (2): Write a function that compute the (??) = ? ???????? ?? ??
=?? , and then
estimate its time complexity using operations count method.
Solution:
Function Peval(coeff: ElemList; n: integer; var x: real): real;
Var y, val: real;
i: integer;
begin
y:=1; val:=coeff[0];
For i:=1 to n do
Begin
y := y * x;
Val := val + y * coeff[i];
End;
Peval:= val;
End;
Suppose we estimate its time complexity by the number of addition and
multiplication performed inside the For loop. We shall use the degree n as the
instance characteristic. The For loop is entered a total of n times, and each
time one addition and two multiplications are done.(this operation count
excludes the add performed each time the loop variable i is incremented). The
number of additions is n, and the number of multiplications is 2n.
There is another way to write the above function as follow:
Function Peval_Horner(coeff: ElemList; n: integer; var x: real): real;
Var val: real;
i: integer;
begin
val:=coeff[n];
For i:=1 to n do
Algorithm Design And Analysis Asst. Prof. Ali Kadhum Idrees
Department of Computer Science College 6 of Science for Women
val := val * x + y * coeff[n-i];
Peval_Horner := val;
End;
Using the same measure as used by the function Peval , we estimate its
complexity as n additions and n multiplications. Since Peval performs the
same number of additions but twice as many multiplications as does
Peval_Horner to be faster.
Homework:
1- Write a function that return the factorial of any positive number , and
then estimate its time complexity using method of operations count.
2- Write a function for the sequential search, and then estimate its time
complexity using method of operations count.
3- Write an algorithm for the selection sort, and then estimate its time
complexity using method of operations count.