NMJ 20003

ALGORITHM & DATA STRUCTURES

ANALYSIS OF
ALGORITHMS
 Outline

• Efficiency of algorithms
• Apriori analysis
• Asymptotic notations
• Time complexity of an algorithm using O notation
• Polynomial Vs Exponential algorithms
• Average, best and worst case complexities
• Analyzing recursive programs
 Efficiency of algorithms

 The performance of algorithms can be measured on the

scales of :
1. Time
 Measured by time complexity
 a function of the running time of the algorithm or program

2. Space
 Measured by space complexity
 a function of the space needed by the algorithm or program to
run to completion
 Efficiency of algorithms

 Time complexity can be computed by

1. Empirical / posteriori approach
 implementing the complete algorithms and executing them
on a computer for various instances of the problem
2. Theoretical / apriori approach
 mathematically determining the resources such as time and
space needed by the algorithm, as a function of a
parameter related to the instances of the problem
considered
 Efficiency of algorithms

 Disadvantage of empirical / posteriori testing

approach
 Dependent on various other factors – machine on which the
program is executed, the programming language, skills of the
programmer
 Permits study on input instances of moderate size
 Advantages of apriori approach
 Independent on machine, language and program

 Permits study on any input instance of any size

 Apriori Analysis

 Apriori estimation is interested in the following for the

computation of efficiency:
(i) the number of times the statement is executed in the
program, known as the frequency count of the statement,
and
(ii) the time taken for a single execution of the statement

 However, time taken for a single execution of the

statement is machine dependent. Thus, frequency
count is consider to compute the efficiency of the
program
 Frequency count

Program statements Frequency

Program segment A count
…
…
x = x + 2; 1
x = x + 2;
… …
Total frequency count 1
 Program segment B
Program statements Frequency count
… …
for k = 1 to n do
for k = 1 to n do (n+1)
x = x + 2;
end x = x + 2; n
… end n
…
Total frequency count 3n+1
Program segment C Program statements Frequency
count
… …
for j = 1 to n do for j = 1 to n do (n+1)
for k = 1 to n do
for k = 1 to n do n(n+1)
x = x + 2;
end x = x + 2; n2
end end n2
… end n
…
Total frequency count 3n2+3n+1
 Asymptotic Notation

 It is a function that represent the time and

complexity of a program .
 Employed by apriori analysis to express the time
complexity
 Asymptotic Notations
f (n) = O( g (n)) ( read as f of n is “big oh” of g of n), iff
there exists a positive integer n0 and a positive number C
such that f (n)  C g (n) , for all n  n0 .

f (n) = ( g (n)) ( read as f of n is omega of g of n), iff there exists a positive integer n0 and a

positive number C such that f (n)  C g (n) , for all n  n0 .

f (n) = ( g (n)) (read as f on n is theta of g of n) iff there

exist two positive constants c1 and c2 , and a positive integer
n0 such that c1 g (n)  f (n)  c2 g (n) for all n  n0 .

f (n) = o( g (n)) (read as f of n is “little oh” of g of n) iff

f (n) = O( g (n)) and f (n)  ( g (n)) .
 Big O

 Simplified analysis of an algorithm efficiency

 To measure the performance of any algorithm by
providing the order of growth of the function
 Time Complexity Of An Algorithm Using O
Notation
f(n) = 2 O (1)
O(1) constant f(n) = 3
O(n) linear
f(n) = 2n + 3 O(n)
O(n2) quadratic f(n) = 500n + 15
O(n3) cubic
O(logn) logarithmic
O(nk) polynomial time
O(2n), O(3n), in general O(kn) exponential time
complexities
 Big O

 O(1) Constant - no loops.

 O(log N) Logarithmic - usually searching algorithms have log n if they are

sorted (Binary Search).

 O(n) Linear - for loops, while loops through n items.

 O(n log(n)) Log Linear - usually sorting operations.

 O(n^2) Quadratic - every element in a collection needs to be compared to ever

other element. Two nested loops.

 O(2^n) Exponential - recursive algorithms that solves a problem of size N.

 O(n!) Factorial - you are adding a loop for every element

 Time Complexity Of An Algorithm Using O
Notation

Big O:
 Ignore constant
 2n -> O(n)
 Ignore low order terms

Some of the commonly occurring time complexities in their

ascending orders of magnitude are listed below:

O(1)≤ O(log n) ≤ O(n) ≤ O([Link] n) ≤ O(n2) ≤ O(n3) ≤ O(2n)

 Polynomial Vs Exponential Algorithms

150

Output of the computing time function

100
1

Polynomial 2
algorithms
are more 50 3
efficient
that 4
exponential
algorithm
0
1 2 3 4 5 6 7 8 9 10 11 12
Input size

1: n2 2: 2n 3: n log2n 4: log2n

Growth rate of some computing time functions

 Comparison of polynomial and exponential
algorithms

Size 10 20 50

Time complexity function

n2 10-4 sec 4 X 10-4 sec 25 X 10-4 sec

n3 10-3 sec 8 X 10-3 sec 125 X 10-3 sec

2n 10-3 sec 1 sec 35 years

3n 6 X 10-2 sec 58 mins 2 X 103
centuries
 Things that can cause time in a function

• Operations (+, -, *, /)
• Comparisons (<, >, ==)
• Looping (for, while)
• Outside Function call (function())
 Average, Best And Worst Case Complexities

 That input instance (or instances) for which the algorithm

takes the maximum possible time is called the worst case
and the time complexity in such a case is referred to as worst
case time complexity

 That input instance for which the algorithm takes the

minimum possible time is called the best case and the time
complexity in such a case is referred to as best case time
complexity.

 All other input instances which are neither of the two are
categorized as average cases and the time complexity of the
algorithm in such cases is referred to as average case
complexity.
 Average, Best And Worst Case Complexities
Example
Algorithm To sequentially search for the first occurring even
number in the list of numbers given
Input 1: -1, 3, 5, 7, -5,7,11,-13,17,71,21,9,3,1,5,-23,-29,33,35,37,40

Input 2: 6, 17, 71, 21, 9,3, 1,5,-23,3,64,7,-5,7,11,33,35,37,-3,-7,11

Input 3: 71, 21, 9, 3, 1,5,-23,3,11,33,36,37,-3,-7,11,-5,7,11,-3,17,22

Determine the efficiency of the algorithm for the input instances

in terms of number of comparisons done before the first
occurring even number is retrieved.

The best,the worst???

 Average, Best And Worst Case Complexities

Input 1: -1, 3, 5, 7, -5,7,11,-13,17,71,21,9,3,1,5,-23,-29,33,35,37,40

Input 2: 6, 17, 71, 21, 9,3, 1,5,-23,3,64,7,-5,7,11,33,35,37,-3,-7,11

Input 3: 71, 21, 9, 3, 1,5,-23,3,11,33, 36, 37,-3,-7,11,-5,7,11,-3,17,22

Best possible case – Worst possible case

quickest execution of Average as it takes the
the algorithm case longest possible time
to complete

O(1) O(n)
 Big O and Style Guidelines

 Big O is similar to saying the runtime is

less than or equal to Big O notation.
⎯⎯ O(f) is an upper bound
 Don't use constants or lower-order terms
⎯⎯ O(n2 + n) should be written O(n2)
O(5500n) should be written O(n)
O(2.5n) should be written O(n)
 Properties of Big-O

Summarizing two main properties

If f(n) is a sum of several terms, the one with the largest growth
rate is kept, and all others omitted

If f(n) is a product of several factors, any constants (terms in the

product that do not depend on n) are omitted
 Properties of Big-O

We can drop coefficient

Example:

f(n) = 100*n
then f(n) is O(n)
 Summation of same Orders

The property is useful when an algorithm contains

several loops of the same order

Example:

f(n) is O(n)
f2(n) is O(n)
then f(n) + f2(n) is O(n) + O(n), which is O(n)
 Summation of different Orders

This property works because we are only concerned

with the term of highest growth rate

Example:

f1(n) is O(n2)
f2(n) is O(n)
so f1(n) + f2(n) = n2 + n is O(n2)
 Runtimes with for loops

int n = 1000;
int[] x = new int[n];

for(int j = 0; j < n; j++)

x[j] = 0;
End
 Runtimes with for loops

int n = 1000;
int[] x = new int[n];

int sum = 0;
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
sum += j * k;
End
End
 Run times with for loops

 O(n3)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
for (int l = 0; l < n; l++)
sum += j * k * l;
 O(n)
for (int j = 0; j < n; j++)
sum++;
for (int j = 0; j < n; j++)
sum--;
 Analyzing Recursive Programs
 Important in Computer Science, most algorithms applies recursion

Recursive Procedure
-Recursive functions
-Recursive programs
 Analyzing Example
Recursive Programs

 A recursive procedure to compute factorial of a number n is

shown below:
n! =1, if n =1 (base criterion)
n! = n. (n-1)!, if n >1
n! calls (n-1)! for its definition

The pseudo-code recursive function for computation of n! is

shown below:
function factorial (n)
1-2. if (n==1) then factorial = 1;
or else
3. factorial = n* factorial (n-1);
and end factorial.
 Apriori Analysis of analysis functions

 Apriori analysis of recursive function is different

from that of iterative functions
 Time complexity for recursive functions - need to
formulate recurrence relations that define the
behaviour of the function
 Use unknown time function T(n), n = size of the arguments
 Apriori analysis of recursive functions
(Factorial(n))

function factorial (n)

1-2. if (n=1) then factorial = 1; O(1)
or else
3. factorial = n* factorial (n-1); O(1) + T(n -1)
and end factorial.

T(n) = c + T(n-1), if n > 1

=d if n <= 1
Apriori analysis of recursive functions
(Factorial(n))
 Example:The Tower of Hanoi puzzle

Peg Source(S) Peg Intermediary(I) Peg Destination(D)

Tower of Hanoi puzzle ( initial configuration)

a. Transfer disk in Peg S to Peg D, maintain the same order
b. Move 1 disk at one times, never can a large disk on smaller disk during transfer
c. Peg I is for intermediate use during transfer
function TRANSFER(N, S, I, D)

/* N disks are to be transferred from peg S to peg D with peg I as the

intermediate peg*/

if N is 0 then exit();
else
{ TRANSFER(N-1, S, D, I); /* transfer N-1 disks from
peg S to peg I with peg D as the intermediate peg*/

Transfer disk from S to D; /* move the disk which is

the last and the largest disk, from peg S to peg D*/

TRANSFER(N-1, I, S, D); /* transfer N-1 disks from

peg I to peg D with peg S as the intermediate peg*/
}
end TRANSFER.
 Let T(n) = running time of transfer(n, S, I, D)

T(N) =0 , if N = 0
= 2.T(N-1)+1 if N > 0
Apriori analysis of recursive functions
(Tower of Hanoi)
 Exercise

 Find the frequency count & time complexity of the

following program fragment:

 1. for i = 20 to 30
 2. for j = i to n
 3. am = am + 1;
 4. end
 5. end
 Conclusion

 The efficiency of a program or an algorithm is measured by

computing its time and/or space complexities. The time
complexity of an algorithm is a function of the running time of
the algorithm and the space complexity is a function of the
space required by it to run to completion.
 The time complexity of an algorithm can be measured using
Apriori analysis or Posteriori testing.
 The efficiency of algorithms is not just dependent on the input
size but is also dependent on the nature of the input which
results in worst, best and average case complexities
 Polynomial algorithms are highly efficient when compared to
exponential algorithms
 Apriori analysis of recursive algorithms calls for the
formulation of recurrence relations and obtaining their closed
form solutions, before expressing them using appropriate
asymptotic notations