Performance Analysis of Algorithms

Data Structures
Performance Analysis
Fundamental Concepts
Some fundamental concepts that you should
know:
Dynamic memory allocation.
Recursion.
Performance analysis.
There are problems and algorithms to solve them.
Problems and problem instances.
Example: Sorting data in ascending order.
Problem: Sorting
Problem Instance: e.g. sorting data (2 3 9 5 6 8)
Algorithms: Bubble sort, Merge sort, Quick sort,
Selection sort, etc.
Which is the best algorithm for the problem? How

do we judge?
3
Two criteria are used to judge algorithms:
(i) time complexity (ii) space complexity.
Space Complexity of an algorithm is the
amount of memory it needs to run to
completion.
Time Complexity of an algorithm is the
amount of CPU time it needs to run to
completion.
4
Space Complexity
Memory space S(P) needed by a program P,
consists of two components:
A fixed part: needed for instruction space (byte
code), simple variable space, constants space
etc. c
A variable part: dependent on a particular
instance of input and output data.
Sp(instance)
S(P) = c + Sp(instance)
5
Space Complexity: Example 1

1. Algorithm abc (a, b, c)
2. {
3.
return a+b+b*c+(a+b-c)/(a+b)+4.0;
4. }
For every instance 3 computer words

required to store variables: a, b, and c.
Therefore Sp()= 3. S(P) = 3.
6
Space Complexity: Example 2

1. Algorithm Sum(a[], n)
2. {
3.
s:= 0.0;
4.
for i = 1 to n do
5.
s := s + a[i];
6.
return s;
7. }
Space Complexity: Example 2.

Every instance needs to store array a[] & n.
Space needed to store n = 1 word.
Space needed to store a[ ] = n floating point
words (or at least n words)
Space needed to store i and s = 2 words
Sp(n) = (n + 3). Hence S(P) = (n + 3).
Time Complexity
Time required T(P) to run a program P also
consists of two components:
A fixed part: compile time which is
independent of the problem instance c.
A variable part: run time which depends on the
problem instance tp(instance)
T(P) = c + tp(instance)
9
Time Complexity
How to measure T(P)?
Measure experimentally, using a stop watch
T(P) obtained in secs, msecs.
Count program steps T(P) obtained as a step
count.
Fixed part is usually ignored; only the

variable part tp() is measured.
10
Time Complexity
What is a program step?
a+b+b*c+(a+b)/(a-b) one step;
comments zero steps;
while (<expr>) do step count equal to
the number of times <expr> is executed.
for i=<expr> to <expr1> do step count
equal to number of times <expr1> is checked.
11
Time Complexity: Example 1

Statements
1
2
3
4
5
6
7
Algorithm Sum(a[],n)
{
S = 0.0;
for i=1 to n do
s = s+a[i];
return s;
}
S/E
Freq.
Total
0
0
1
1
1
1
0
1
n+1
n
1
-
0
0
1
n+1
n
1
0
2n+3
12
Time Complexity: Example 2

Statements
1
2
3
4
5
6
7
Algorithm Sum(a[],n,m)
{
for i=1 to n do;
for j=1 to m do
s = s+a[i][j];
return s;
}
S/E Freq.
Total
n+1
n+1
n(m+1)
n(m+1)
nm
nm
2nm+2n+2
13
Performance Measurement
Which is better?
T(P1) = (n+1) or T(P2) = (n2 + 5).
T(P1) = log (n2 + 1)/n! or T(P2) = nn(nlogn)/n2.
Complex step count functions are difficult

to compare.
For comparing, rate of growth of time and
space complexity functions is easy and
sufficient.
14
Big O Notation
Big O of a function gives us rate of growth of
the step count function f(n), in terms of a simple
function g(n), which is easy to compare.
Definition: [Big O] The function f(n) = O(g(n))
(big oh of g of n) iff there exist positive
constants c and n0 such that f(n) <= c*g(n) for all
n, n>=n0. See graph on next slide.
Example: f(n) = 3n+2 is O(n) because 3n+2 <= 4n
for all n >= 2. c = 4, n0 = 2. Here g(n) = n.
15
Big O Notation
= n0
16
Big O Notation
Example: f(n) = 10n2+4n+2 is O(n2)
because 10n2+4n+2 <= 11n2 for all n >=5.
Example: f(n) = 6*2n+n2 is O(2n) because
6*2n+n2 <=7*2n for all n>=4.
Algorithms can be: O(1) constant; O(log
n) logrithmic; O(nlogn); O(n) linear;
O(n2) quadratic; O(n3) cubic; O(2n)
exponential.
17
Big O Notation
Now it is easy to compare time or space
complexities of algorithms. Which
algorithm complexity is better?
T(P1) = O(n) or T(P2) = O(n2)
T(P1) = O(1) or T(P2) = O(log n)
T(P1) = O(2n) or T(P2) = O(n10)
18
Some Results
Sum of two functions: If f(n) = f1(n) + f2(n), and
f1(n) is O(g1(n)) and f2(n) is O(g2(n)), then f(n) =
O(max(|g1(n)|, |g2(n)|)).
Product of two functions: If f(n) = f1(n)* f2(n), and
f1(n) is O(g1(n)) and f2(n) is O(g2(n)), then f(n) =
O(g1(n)* g2(n)).
19

Performance Analysis of Algorithms

Uploaded by

Copyright:

Available Formats

Performance Analysis of Algorithms

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Performance Analysis of Algorithms

Uploaded by

Copyright:

Available Formats

Data Structures

Which is the best algorithm for the problem? How

Space Complexity: Example 1

For every instance 3 computer words

Space Complexity: Example 2

Space Complexity: Example 2.

Sp(n) = (n + 3). Hence S(P) = (n + 3).

Fixed part is usually ignored; only the

Time Complexity: Example 1

Time Complexity: Example 2

Complex step count functions are difficult

You might also like