ALGORITHMS – ANALYSIS AND

DESIGN

Lekha A
Computer Applications
ALGORITHMS – ANALYSIS AND
DESIGN

Introduction, Analysis Framework,

Brute Force Method
Analysis Framework

Lekha A
Computer Applications
 ALGORITHMS – ANALYSIS AND DESIGN
Recap

• Fundamentals of Algorithmic Problem Solving

 ALGORITHMS – ANALYSIS AND DESIGN
Analysis

• Analysis is defined as the separation of an intellectual or

substantial whole into its constituent parts for individual study.

• Analysis of algorithm is referred as investigation of an

algorithm with respect to running time and memory space.

 ALGORITHMS – ANALYSIS AND DESIGN
Analysis Framework

• Time efficiency indicates how fast an algorithm runs.

• Space efficiency deals with the extra space the algorithm

needs.

• Now a days the amount of extra space required by a algorithm

is typically not of much concern.

 ALGORITHMS – ANALYSIS AND DESIGN
Measuring an input

• Almost all algorithms run longer on larger inputs.

• It takes longer time for sorting larger arrays, multiplying larger

element matrix .

• It is logical to find efficiency as a function of parameter n

where n is the input size.

• It holds in the case of sorting, searching, and finding list’s

smallest element.
 ALGORITHMS – ANALYSIS AND DESIGN
Measuring an input

• It is also the same in case of spell checking algorithm, where

there is a need to check each character which depends on the

number of character present.

• For such algorithms, computer scientists prefer measuring size

by the number b of bits in the n’s binary representation:

• b = [log 2 n] + 1.
 ALGORITHMS – ANALYSIS AND DESIGN
Units of measuring running time

• Use physical unit of time i.e. second, Milliseconds.

• There are drawback in this approach, the running time

depends on the

• Compiler in developing the machine instruction.

• A program to implement the algorithm.

• The clock speed of the system.

 ALGORITHMS – ANALYSIS AND DESIGN
Units of measuring running time

• Since it is the efficiency of the algorithm it should be

independent of all these factors.

• One possible approach is to count the number of times each

of the algorithm’s operation is executed.

 ALGORITHMS – ANALYSIS AND DESIGN
Units of measuring running time

• Identify the basic operation (the most important operation of

algorithm)

• The basic operation contributes most to the running time

of the algorithm.

• It is the most time consuming operation in the algorithm’s

inner most loop.

 ALGORITHMS – ANALYSIS AND DESIGN
Units of measuring running time

• Example

• Key comparison operation in Searching algorithm

• T (n) ≈ cop C (n)

• n : Input size

• T(n) : Running time

• cop : Execution time for basic operation

• C(n) : no of times the basic operation is executed.

 ALGORITHMS – ANALYSIS AND DESIGN
Units of measuring running time

• The count C(n) does not contain any info about operations

that are not basic.

• This count is often computed only approximately.

• Constant cop is also an approximation.

 ALGORITHMS – ANALYSIS AND DESIGN
Orders of Growth

• By using small inputs we cannot distinguish the efficient

algorithm from the inefficient ones.

• For example in the case of Euclid’s algorithm the efficiency of

the algorithm becomes clear only in the case of the large

input difference.
 ALGORITHMS – ANALYSIS AND DESIGN
Orders of Growth

n log2 n n n log2 n n2 n3 2n n!
10 3.3 101 3.3 *101 102 103 103 3.6 * 106
• 102 6.6 102 6.6 * 102 104 106 1.3 * 1030 9.3 * 10157
103 10 103 1.0 * 104 106 109
104 13 104 1.3 * 105 108 1012
105 17 105 1.7 * 106 1010 1015
106 20 106 2.0 * 107 1012 1018
 ALGORITHMS – ANALYSIS AND DESIGN
Orders of Growth

• The function growing the slowest among these is the

logarithmic function.

• Therefore we should expect a program implementing an

algorithm with logarithmic basic-operation.

• On the other end the exponential and the factorial function

grows fast.
 ALGORITHMS – ANALYSIS AND DESIGN
Recap

• Analysis Framework

• Measuring an Input

• Units of measuring running time

• Orders of Growth
Thank you

Lekha A
Computer Applications