ALGORITHMS – ANALYSIS AND

DESIGN

Lekha A
Computer Applications
ALGORITHMS – ANALYSIS AND
DESIGN
Introduction, Analysis Framework,
Brute Force Method
Efficiency of an algorithm

Lekha A
Computer Applications
 ALGORITHMS – ANALYSIS AND DESIGN
Recap

• Analysis Framework

• Measuring an Input

• Units of measuring running time

• Orders of Growth
 ALGORITHMS – ANALYSIS AND DESIGN
Efficiency

• There are three categories of time efficiencies that the

algorithms can be categorized into.

• Worst-case

• Best-case

• Average-case
 ALGORITHMS – ANALYSIS AND DESIGN
Efficiency

• The efficiency of the algorithm is measured as a function of a

parameter indicating the size of the input to the algorithm.

• For some algorithms the running time depends on the

specifics of a particular input.

• Example

• Sequential search
 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

•//searches for a given value in a given array by sequential search

•//Input: An array A[0..n — 1] and a search key K

•//Output: Returns the index of the first element of A that

•// matches K or -1 if there are no matching elements

 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• i ←0

• while i < n and A[i] ≠ K do

• i← i+1

• if i<n return i

• else return -1
 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• The running time of this algorithm will be different for the

same list size n.

• There are no matching elements.

• The first matching element happens to be the last one on

the list.
ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• It makes the largest number of key comparisons

among all possible inputs of size n.

• Cworst(n) = n
 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• The worst-case efficiency of an algorithm is its efficiency for

the worst-case input of size n.

• It is the input of size n that make the algorithm run for the

longest possible time among all inputs.

• It guarantees that for any instance of size n, the running

time will not exceed Cworst (n) .

 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• The algorithm’s efficiency for the best case input of size n, is

an input (or inputs) of size n for which the algorithm runs the

fastest among all possible inputs of that size.

• In the case of sequential search , best case inputs will be

lists of size n with the first elements equal to search key;

accordingly,

• Cbest (n) = 1
 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• The best case doesn’t mean the small input; it means the

input of size n for which the algorithm runs the fastest.

• The analysis of the best-case efficiency is not nearly as

important as that of the worst-case efficiency.

 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• The average case efficiency of an algorithm is its efficiency for

the “random” or “typical” input of size n.

• Cavg (n) = p (n+1)/2 +n (1-p)

 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• Standard Assumptions

• The probability of a search is equal to p (0≤p≤1)

• The probability of first match in ith position is same for

every i i.e. p/n.

• where i is the number of key comparison

 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• Probability of unsuccessful search = (1-p).

p p p p
Cavg (n) = [1( )+ 2( ) + 3( )........ + n( )] + n(1 − p)
n n n n
p
= (1 + 2 + 3 + ... + n) + n(1 − p )
n
p  ( n + 1) 
=  n  + n(1 − p )
n  2 
( n + 1)
= p + n(1 − p )
2

• This is quite reasonable.

 ALGORITHMS – ANALYSIS AND DESIGN
Algorithm – Sequential Search (A[0..n-1], k)

• If p=1 (successful search) the average number of key

comparisons is

• n+1/2 ≈ half of the list.

• If p=0(unsuccessful search) then number of comparison is n.

• Finding average case efficiency is difficult but for some

algorithm it is important.
 ALGORITHMS – ANALYSIS AND DESIGN
Efficiencies - Amortized

• It applies not to a single run of an algorithm but rather to a

sequence of operations performed on the same data

structure.

• It turns out that in some situations a single operation can be

expensive, but total for an entire sequence of n operation is

always significantly better than worst-case efficiency of that

single operation multiplied by n.

 ALGORITHMS – ANALYSIS AND DESIGN
Recap

• Efficiency

• Worst-case efficiency

• Best-case efficiency

• Average-case efficiency

• Example
Thank you

Lekha A
Computer Applications