Algorithm

Analysis &
Importance

Algorithm
Importance

Computer Science Faculty - Software

Algorithm and its
Importance

Analysis of
Engineering Algorithms
Analysis of

Analysis of Algorithms Algorithms

Analysis of Algorithms‘ Course Lectures

( Algorithm Analysis & Importance )

Ali Shah Saber

[email protected] | telegram: @alishahsaber
Fall, 2024
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Session Overview Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
Algorithms
1 Algorithm Importance Analysis of
Algorithms

Algorithm and its Importance

2 Analysis of Algorithms
Analysis of Algorithms

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Review of Algorithm Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

• Clearly specified set of instructions. Analysis of

Algorithms
• Step-by-step procedure. Analysis of
Algorithms

• Computational steps that transfer input to output.

• Almost everything that you do with a computer
relies in some way on an algorithm.
• A program is an algorithm that has been customized
to solve a specific task under a specific set of
circumstances using a specific language.
• An algorithm is a finite set of precise instructions for
performing a calculation or solving a problem.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Techniques of Expressing Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Algorithms can be expressed in many ways: Analysis of

Algorithms
• (1) Detailed Algorithm , Analysis of
Algorithms

• (2) Pseudo-code,
• (3) Flow charts.

Simple Examples
• (1) Write an algorithm to determine a student’s final
grade and indicate whether it is passing or failing.
• (2) The final grade is calculated as the average of
four marks.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Importance of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
Computer process a large amount of data. The program Algorithms
must terminates within a reasonable amount of time. Analysis of
Algorithms

The time is very important when we run a program on a

large amount of input. Algorithms solve the same
problem often differ dramatically in their efficiency.

These differences can be much more significant than

differences due to hardware and software.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Importance of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
A program is an implementation of an algorithm. Analysis of
Algorithms
Analysis of
Algorithms

Suppose computers were infinitely fast and computer

memory was free. Would you have any reason to study
algorithm?

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Importance of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
A program is an implementation of an algorithm. Analysis of
Algorithms
Analysis of
Algorithms

Suppose computers were infinitely fast and computer

memory was free. Would you have any reason to study
algorithm?

The answer is yes:

• Implementation to be within the bounds of good
software engineering practice.
• Select the easiest implementation.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Importance of Algorithms Analysis &
Importance

Algorithm
Importance
The speed of hardware computation of basic operations Algorithm and its

has been improved dramatically, but efficiency matters Importance

Analysis of
more than ever today. Algorithms
Analysis of
Algorithms

This is because our ambition for computer applications

has grown with computer power.

Many are as demand a great increase in speed of

computation.
• Examples include the simulation of continuous
systems, high resolution graphics, and the
interpretation of physical data, medical applications,
and information systems.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Importance of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
On the other hand (and more importantly), an algorithm Algorithms
may be so inefficient that, even with computation speed Analysis of
Algorithms

vastly increased, it would not be possible to obtain a

result within a useful period of time.

The time that many algorithms take to execute is a

non-linear function of the input size.
• This can reduce their ability to benefit from the
increase in speed when the input size is large.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analysis of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
A field of computer science. Describe the complexity of Analysis of
algorithms. Algorithms
Analysis of
Algorithms

An algorithm is said to be correct if, for every input

instance, it halts with the correct output.

Once an algorithm is given for a problem and determined

to be correct, the next step is to determine the amount of
resources.
• This step is called algorithm analysis.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analysis of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
Analyzing an algorithm determines the amount of time Analysis of
and space that algorithm takes to execute. Two questions Algorithms
Analysis of
we always ask about algorithm: Algorithms

• Does it work correctly?

• How long does it take?

How can we say that one algorithm performs better than

another?
• Quantify the resources required to execute: (1) Time,
(2) Memory, (3) I/O, (4) Bandwidth

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analysis of Algorithms Analysis &
Importance

Computer scientists use algorithm analysis to

determine: Algorithm
Importance
• How to estimate the running time. Algorithm and its
Importance

• Techniques that reduce the running time. Analysis of

Algorithms
• A mathematical framework to describe the running Analysis of
Algorithms

time of algorithm.
• How much memory space the computer needs for
data and code?
• Whether an algorithm produces correct calculations.
• How complex a program is?
• How much longer does the Algorithm take when the
size of data increase?
• How well it deals with unexpected results?
• The ability to do an analysis usually provides insight
into designing efficient algorithms.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Why Study Analysis of Algorithms? Analysis &
Importance

Algorithm
Importance
• A toolbox of standard algorithmic techniques. Algorithm and its
Importance

• Methods for analyzing algorithm efficiency. Analysis of

Algorithms
• Efficient algorithm lead to efficient program. Analysis of
Algorithms

• Efficient programs make better use of hardware.

• The efficiency of an algorithm is estimated by its
performance.
• The performance of an algorithm can be measured by
the time and the space required.
• The time and space requirement of an algorithm is
called the computational complexity of the algorithm.
• The greater the amount of the time and space
required, the more complex is the algorithm.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Why Measure Time in Analysis of Analysis &
Importance

Algorithms?
Algorithm
Importance
Algorithm and its
Importance

Which measure is more important? Analysis of

Algorithms

Answer often depends on the limitations of the technology Analysis of

Algorithms

available at time of analysis.

Normally we are concerned with the time rather than

space. The reasons are that:
• Firstly it becomes easier and cheaper to obtain space.
• Secondly techniques to achieve space efficiency by
spending more time are available.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Measuring Time in Analysis of Algorithms? Analysis &
Importance

Algorithm
How to Measure Time in Analysis of Algorithms Importance
Algorithm and its

• Analyzing an algorithm determines the amount of Importance

Analysis of
“time” that algorithm takes to execute. Algorithms

• This is not really a number of seconds or any other

Analysis of
Algorithms

clock measurement but rather an approximation of

the number of operations that an algorithm performs.
• The number of operations is related to the execution
time, so we will sometimes use the word time to
describe an algorithm’s computational complexity.
• The actual number of seconds it takes an algorithm
to execute on a computer is not useful in our analysis
because we are concerned with the relative efficiency
of algorithms that solve a particular problem.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Experimental Approach of Algorithm Analysis Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
The best way if feasible. Analysis of
Algorithms
Reasons which reject the use of Experimental Analysis of
Algorithms

Approach

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Experimental Approach of Algorithm Analysis Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
The best way if feasible. Analysis of
Algorithms
Reasons which reject the use of Experimental Analysis of
Algorithms

Approach
• We would like to eliminate the bad ones early.
• This method does not enable you to reason about
whether the efficiency can be improved.
• This method does not give you any insight into how
the program will perform if run on different hardware
or under different conditions.
• The effort involve program and testing.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Experimental Approach of Algorithm Analysis &
Importance

Analysis Cont.
Algorithm
Importance
Algorithm and its
Importance
The best way if feasible.
Analysis of
Algorithms
Reasons which reject the use of Experimental Analysis of
Algorithms

Approach Cont.
• May be one Algorithm is not better written.
• Experiments can be done only on a limited set of test
inputs.
• We will have difficulty comparing the experimental
running times of two algorithms unless the
experiments were performed in the same hardware
and software environments.
• We have to fully implement and execute an algorithm
in order to study its running time experimentally.
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analytic Approach of Algorithm Analysis Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
Algorithms
• An algorithm consists of a set of instructions. Analysis of
Algorithms

• The time complexity is the number of steps,

irrelevant to the real time.
• We do not measure the time complexity by the
running time of a program.
• The unit of the time complexity is the number of
steps.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analytic Approach of Algorithm Analysis Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
• Analytic approach uses a high-level description of the Algorithms
Analysis of
algorithm instead of an implementation. Algorithms

• It characterizes running time as a function of the

input size. Also it takes into account all possible
inputs.
• It allows us to evaluate the speed of an algorithm
independent of the hardware/software environment.
• Using this method we can develop a general way of
analyzing the running times of algorithms.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Ananlysis of Algorithms Analysis &
Importance

Algorithm
Importance

Different input requires different amount of resources. Algorithm and its

Importance

Instead of dealing with input itself, we prefer to deal with Analysis of

Algorithms
the Size of Input. Analysis of
Algorithms

Size of Input
The amount of memory required for representing the
input with respect to a fixed coding scheme.

Examples
• For an array => The size can be considered as the
number of its elements...
• For a graph => The size can be considered as the
number of vertices or edges...

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analysis of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance
• Predicting the amount of resources that the Analysis of
algorithm requires. Algorithms
Analysis of

• We expect that the amount of resources used by any

Algorithms

algorithm growth with respect to the input size.

Should be independent from the current technology

(Hardware, Programming Languages, etc.).

Should be independent from the way of implementing the

algorithm.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analysis of Algorithms Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
Algorithms
• Measure the required time (time complexity) and Analysis of
Algorithms
memory (space complexity).
• Best case: Measuring the required amount of
resources for easy instances.
• Worse case: Measuring the required amount of
resources for hard instances.
• Average case: Measuring the required amount of
resources for all instances divided by the number of
instances.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

Algorithm
Importance
Algorithm and its
Deciding what to count involves two steps: Importance

Analysis of
• The first is choosing the significant operations. Algorithms
Analysis of

• The second is deciding which of those operations are Algorithms

integral to the algorithm and which are overhead.

There are two classes of operations that are typically

chosen for the significant operation:
• Comparison
• Arithmetic

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

Algorithm
Comparison Operators Importance
Algorithm and its
• The comparison operators are all considered Importance

Analysis of
equivalent and are counted in algorithms such as Algorithms
searching and sorting. Analysis of
Algorithms

• Comparison operations include equal, not equal, less

than, greater than, less than or equal, and greater
than or equal.

Arithmetic operators
1 Additive; Additive operators include addition,
subtraction, increment, and decrement.
2 Multiplicative; Multiplicative operators include
multiplication, division, and modulus.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

Algorithm
Importance
Algorithm and its
Importance

Analysis of
In fact, some algorithms are viewed more favorably if they Algorithms
Analysis of
reduce the number of multiplications even if that means a Algorithms

similar increase in the number of additions.

Logarithms and geometric functions that are used in

algorithms would be another group even more time
consuming than multiplications because those are
frequently calculated by a computer through a power
series.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

Primitive Operations
• Assigning a value to a variable. Algorithm
Importance

• Calling a method.
Algorithm and its
Importance

Analysis of
• Performing an arithmetic operation (for example, Algorithms
Analysis of
adding two numbers). Algorithms

• Comparing two numbers.

• Indexing into an array.
• Following an object reference.
• Returning from a method.

Instead of trying to determine the specific execution time

of each primitive operation, we will simply count how
many primitive operations are executed, and use this
number as a measure of the running-time of the
algorithm. . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

Algorithm
Loops Importance
Algorithm and its
Importance

• The running time of the statements inside the for Analysis of

Algorithms
loop times the number of iterations. Analysis of

• The total running time of a statement inside a nested

Algorithms

loops is the running time of the statement multiplied

by the product of the loops.

If/else
1 For the fragment if (condition) S1 else S2, the
running time of an if/else statement is never more
than the running time of the test plus the larger of
the running times of S1 and S2.

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

Algorithm
Calculation Examples Importance
Algorithm and its
Importance
• e.g. Calculate number of steps of bellow code(s)? Analysis of
Algorithms
Analysis of

// Algorithm #1 Algorithms

1. x=0;
2. for(i=0; i<n; i++)
3. x++;

// Algorithm #2
1. x=0;
2. for(i=0; i<n; i++)
3. for(i=0; i<n; i++)
4. x++;

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
What to Count and Consider? Analysis &
Importance

• Compute sum(k=1 to k=n), where n is an integer. Algorithm

Importance
Algorithm and its
Importance

// Algorithm #3: Compare with Algorithm #4 Analysis of

1. int first_sum_algorithm(int n){ Algorithms
Analysis of

2. Int sum=0; Algorithms

3. for (int k=1; k<=n; k++){

4. sum=sum+k;
5. }
6. return sum;
7. }
// Algorithm #4: Compare with Algorithm #3
1. int second_sum_algorithm (int n){
2. int sum;
3. return(n*(n+1)/2);
4. }
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Algorithm
Analysis of Algorithms Analysis &
Importance

Algorithm
By analyzing several candidate algorithms for a specific Importance

problem, the most efficient one can be easily identified. Algorithm and its
Importance

Analysis of
Classifying the Functions Algorithms
Analysis of
Algorithms
There are infinitely many functions. In order to compare
them with each other, we prefer to classify them as simple
functions without loss of their properties. In fact we want
to choose one simple function for each class of functions

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 The End
Questions? Comments?

. . . .... .... .... . . . . .