Algorithm Analysis

BLG221E
Analysis of Algorithms
Most algorithms transform input objects into output objects.

Input Algorithm Output

An algorithm is a step-by-step procedure for

solving a problem in a finite amount of time.
Running Time
 Most algorithms transform
input objects into output best case
objects. average case

 The running time of an

worst case
120
algorithm typically grows
with the increase of input 100

size.

Running Time
80

 Average case time is often 60

difficult to determine.
 We focus on the worst
40

case running time. 20

 Easier to analyze 0
 Crucial to applications such as 1000 2000 3000 4000

games, finance and robotics Input Size

Algorithmic Performance
There are two aspects of algorithmic performance:

Time
 Instructions take time.
How fast does the algorithm perform?
What affects its runtime?

Space
 Data structures take space
What kind of data structures can be used?
How does the choice of data structure
affect the runtime?

How can we analyze the performance of an Algorithm?

Analysis of Algorithms is the area of computer
science that provides tools to analyze the efficiency of
algorithms.
Comparing time performance
analysis of two algorithms

Complexity of Algorithms
[Link] Complexity: Analysis of the time required to solve a
problem of a particular input size (problem size).

[Link] Complexity: Analysis of the computer memory required

to solve a problem of a particular input size (problem size).
Space Complexity
Its the amount of memory space required by the algorithm,
during the course of its execution. Space complexity must be
taken seriously for multi-user systems and in situations where
limited memory is available.

An algorithm generally requires space for following

components :
Instruction Space : Its the space required to store the executable
version of the program. This space is fixed, but varies depending
upon the number of lines of code in the program.
Data Space : Its the space required to store all the constants and
variables value.
Environment Space : Its the space required to store the
environment information needed to resume the suspended function.
Time Complexity is a way to represent the amount of time
needed by the program to run to completion. We will study this in
details in our section.

Time Complexity Example (Linear Search Algorithm):

Recall that the linear search algorithm go through the list from
the beginning of the list until reaching the number (3) or the
end of list.

Determine if 3 is in the following lists

A= { 1 4 8 -1 2 }
B= { 3 4 8 6 5 }
C= { 1 2 4 9 10 11 12 14 19 10 -11 0 }
D= { 1 3 2 4 }
For each list ( problem), how much time will the algorithm take
to finish the problem?
Time Complexity Example
A= { 1 4 8 -1 2 } (exit at the end of the list)
B= { 3 4 8 6 5 } (exit at the beginning of the list)
C= { 1 2 4 9 10 11 12 14 19 10 -11 0 }
D= { 1 3 2 4 } (exit after comparing two elements)

List B will finish before lists A, C and D, even though list B is

longer than D. List C will take the longest to finish.

Clearly, the time that the algorithm takes to finish

1. Depends on the size of the problem (list).
2. Even for problems of the same size, there are worst-
case, best case, and average case.
How do we compare the time efficiency of two
algorithms that solve the same problem?
Naïve Approach: implement these algorithms in a programming
language (C++), and run them to compare their time
requirements. But, comparing the programs (instead of
algorithms) has difficulties.

How are the algorithms coded?

 Comparing running times means comparing the implementations.
We should not compare implementations, because they are
sensitive to programming style.
What computer should we use?
 We should compare the efficiency of the algorithms
independently of a particular computer.

What data should the program use?

 Any analysis must be independent of specific input data.
Analysis of Algorithms
When we analyze algorithms, we should employ mathematical
techniques that analyze algorithms independently of specific
implementations, computers, or data.
To analyze algorithms:
 First, we start to count the number of significant
operations in an algortihm.

 Then, we will express the efficiency of algorithms using

growth functions.
The Execution Time of Algorithms
Each operation in an algorithm (or a program) has a
cost.
 Each operation takes a certain of time.
count = count + 1;  takes a certain amount of time
and it is constant

A sequence of operations:
count = count + 1; Cost: c1
sum = sum + count; Cost: c2

 Total Cost = c1 + c2
The Execution Time of Algorithms (cont.)
Example: Simple If-Statement
Cost Times
if (n < 0) c1 1
absval = -n c2 1
else
absval = n; c3 1

Total Cost <= c1 + max(c2,c3)

Time performance of an algorithm is measured as a

function of the problem size (input size).
The Execution Time of Algorithms (cont.)
Example: Simple Loop
Cost Times
i = 1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
i = i + 1; c4 n
sum = sum + i; c5 n
}

Total Cost = c1 + c2 + (n+1)*c3 + n*c4 + n*c5

 The time required for this algorithm is proportional to n

Time performance of an algorithm is measured as a

function of the problem size.
The Execution Time of Algorithms (cont.)
Example: Nested Loop
Cost Times
i=1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
j=1; c4 n
while (j <= n) { c5 n*(n+1)
sum = sum + i; c6 n*n
j = j + 1; c7 n*n
}
i = i +1; c8 n
}

Total Cost = c1 + c2 + (n+1)*c3 + n*c4 + n*(n+1)*c5+n*n*c6+n*n*c7+n*c8

 The time required for this algorithm is proportional to n2

Complexity
In general, we are not so much interested in the time and
space complexity for small inputs.

For example, while the difference in time complexity between

linear and binary search is meaningless for a sequence
with
n = 10,

but it is gigantic for n = 230.

Algorithm Growth Rates
Time performance of an algorithm is measured as a function of
the problem size (input size).

So, for instance, we say that (if the problem size is n)

 Algorithm A requires n2/5 time units to solve a problem of
size n.
 Algorithm B requires 5*n time units to solve a problem of
size n.

Input Algorithm Output

 Algorithm Growth Rates (cont.)

Time performance of an algorithm is measured

as a function of the problem size (n)

The most important thing to learn is how quickly the algorithm’s time
requirement grows as a function of the problem size.

 Algorithm A requires time proportional to n2.

 Algorithm B requires time proportional to n.

An algorithm’s proportional time requirement is known as growth rate. We can

compare the efficiency of two algorithms by comparing their growth rates.
For example, let us assume two algorithms A and B that solve
the same class of problems.
The time complexity of A is 5,000n, the one for B is 1.1n for
an input with n elements.

Input Size Algorithm A Algorithm B

n 5,000n 1.1n
10 50,000 3
100 500,000 13,781
1,000 5,000,000 2.51041
1,000,000 5109 4.81041392
This means that algorithm B cannot be used for large inputs, while algorithm
A is still feasible.
So what is important is the growth rate of the complexity
functions.
Big-O notation
The growth of functions is usually described using the Big-O
notation.
The idea behind the Big-O notation is to establish an upper boundary
function for large x. This boundary is specified by a function g(x) that is
usually much simpler than f(x).
We accept that C is constant.
f(x)  Cg(x) whenever x > k, because C does not grow with x.

If we want to show that f(x) is O(g(x)), we only need to find one pair
(C, k) (which is never unique).
Big-O notation Time complexity function

Example:

Show that f(x) = x2 + 2x + 1

Big-O notation of
f(x) is O(x2)
For x > 1 we have:

x2 + 2x + 1  x2 + 2x2 + x2
 x2 + 2x + 1  4x2
Therefore, for C = 4 and k = 1:

f(x)  C.g(x) whenever x > k

f(x)  4x2 whenever x > 1
Big-O notation
Question: If f(x) is O(x2), is it also O(x3)?

Yes. x3 grows faster than x2, so x3 grows also faster than

f(x).

We always have to find the smallest simple function g(x) to

define Big-O notation O(g(x)).
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.
A Comparison of Common Growth-Rate Functions
How much better is O(log2n)?

n O(log2n)
16 4
64 6
256 8
1024 (1KB) 10
16,384 14
131,072 17
262,144 18
524,288 19
1,048,576 (1MB) 20
1,073,741,824 (1GB) 30
A Comparison of Growth-Rate Functions (cont.)
Growth-Rate Functions
O(1): Time requirement is constant, and it is independent of the problem’s size.

O(log2n): Time requirement for a logarithmic algorithm increases slowly as the

problem size increases.

O(n): Time requirement for a linear algorithm increases directly with the size of
the problem.

O(n*log2n): Time requirement for a n*log2n algorithm increases more rapidly than
a linear algorithm.

O(n2) Time requirement for a quadratic algorithm increases rapidly with the size
of the problem.

O(n3): Time requirement for a cubic algorithm increases more rapidly with the
size of the problem than the time requirement for a quadratic algorithm.

O(2n): As the size of the problem increases, the time requirement for an
exponential algorithm increases too rapidly.
Example

If an algorithm takes 1 second to run with the problem size

8, what is the time requirement (approximately) for that
algorithm with the problem size 16?

If its order is:

O(1)  T(16) = 1 second
O(log2n)  T(16) = (1*log216) / log28 = 4/3 seconds
O(n)  T(16) = (1*16) / 8 = 2 seconds
O(n*log2n)  T(16) = (1*16*log216) / 8*log28 = 8/3 seconds
O(n2)  T(16) = (1*162) / 82 = 4 seconds
O(n3)  T(16) = (1*163) / 83 = 8 seconds
O(2n)  T(16) = (1*216) / 28 = 28 seconds = 256 seconds
 Properties of Growth-Rate Functions
1. We can ignore low-order terms in an algorithm’s growth-rate
function.
 If an algorithm is O(n3+4n2+3n), it is also O(n3).
 We only use the higher-order term as algorithm’s growth-
rate function.
2. We can ignore a multiplicative constant in the higher-order
term of an algorithm’s growth-rate function.
 If an algorithm is O(5n3), it is also O(n3).

3. O(f(n)) + O(g(n)) = O(f(n)+g(n))

 We can combine growth-rate functions.
 If an algorithm is O(n3) + O(4n), it is also O(n3 +4n2) 
So, it is O(n3).
 Similar rules hold for multiplication.
Some Mathematical Facts
n
n * (n  1) n 2

i 1
i  1  2  ...  n 
2

2

n
n * ( n  1) * ( 2 n  1) n 3


i 1
i 2
 1  4  ...  n 2

6

3

n 1

 2
i 0
i
 0  1  2  ...  2 n 1
 2 n
1
Growth-Rate Functions – Example1
Cost Times
i = 1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
i = i + 1; c4 n
sum = sum + i; c5 n
}

T(n) = c1 + c2 + (n+1)*c3 + n*c4 + n*c5

= (c3+c4+c5)*n + (c1+c2+c3)
= a*n + b

 So, the growth-rate function for this algorithm is O(n)

Growth-Rate Functions – Example2
Cost Times
i=1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
j=1; c4 n
while (j <= n) { c5 n*(n+1)
sum = sum + i; c6 n*n
j = j + 1; c7 n*n
}
i = i +1; c8 n
}

T(n) = c1 + c2 + (n+1)*c3 + n*c4 + n*(n+1)*c5+n*n*c6+n*n*c7+n*c8

= (c5+c6+c7)*n2 + (c3+c4+c5+c8)*n + (c1+c2+c3)
= a*n2 + b*n + c

 So, the growth-rate function for this algorithm is O(n2)

Growth-Rate Functions – Recursive Algorithms
void hanoi(int n, char source, char dest, char spare) { Cost
if (n > 0) { c1
hanoi(n-1, source, spare, dest); c2
cout << "Move top disk from pole " << source c3
<< " to pole " << dest << endl;
hanoi(n-1, spare, dest, source); c4
} }

The time-complexity function T(n) of a recursive algorithm is defined

in terms of itself, and this is known as recurrence equation for T(n).

To find the growth-rate function for a recursive algorithm, we have to

solve its recurrence relation.
Growth-Rate Functions – Hanoi Towers
What is the cost of hanoi(n,’A’,’B’,’C’)?
when n=0
T(0) = c1
when n>0
T(n) = c1 + c2 + T(n-1) + c3 + c4 + T(n-1)
= 2*T(n-1) + (c1+c2+c3+c4)
= 2*T(n-1) + c  recurrence equation
Now, we have to solve this recurrence equation to find the growth-
rate function of hanoi-towers algorithm
Growth-Rate Functions – Hanoi Towers (cont.)
There are many methods to solve recurrence equations, but we will
use a simple method known as repeated substitutions.

T(n) = 2*T(n-1) + c  recurrence equation

= 2 * (2*T(n-2)+c) + c
= 2 * (2* (2*T(n-3)+c) + c) + c
= 23 * T(n-3) + (22+21+20)*c (assuming n>2)
when substitution repeated i times
= 2i * T(n-i) + (2i-1+ ... +21+20)*c
when i=n (when the substitution repetition is equal to problem size)
= 2n * T(0) + (2n-1+ ... +21+20)*c
n 1
= 2n * c1 + (  2i )*c
i 0

= 2n * c1 + ( 2n-1 )*c = 2n * (c1+c) – c

 So, the growth rate function is O(2n)

Simple Complexity Analysis: Loops (with <)
In the following for-loop:

for (int i = k; i < n; i = i + m){

statement1;
statement2;
}
The number of iterations is: (n – k ) / m
The initialization statement, i = k, is executed one time.
The condition, i < n, is executed (n – k) / m + 1 times.
The update statement, i = i + m, is executed (n – k) / m times.
Each of statement1 and statement2 is executed (n – k) / m
times.
Simple Complexity Analysis : Loops (with <=)
In the following for-loop:

for (int i = k; i <= n; i = i + m){

statement1;
statement2;
}
The number of iterations is: (n – k) / m + 1
The initialization statement, i = k, is executed one time.
The condition, i <= n, is executed (n – k) / m + 2 times.
The update statement, i = i + m, is executed (n – k) / m + 1
times.
Each of statement1 and statement2 is executed (n – k) / m + 1
times.
Complexity Examples (1)
int FindMaxElement(int[] array)
{ Cost
int max = array[0]; C
for (int i=0; i<[Link]; i++) C+(n+1)*C+n*C
{
if (array[i] > max)
{ n*(C+C)
max = array[i];
}
}
return max; C
}

Runs in O(n) where n is the size of the array

The number of elementary steps is ~ n
Complexity Examples (3)

decimal Sum3(int n)
{ Cost
decimal sum = 0; C

for (int a=0; a<n; a++) C+(n+1)*C+n*C

for (int b=0; b<n; b++) n*(C+(n+1)*C+n*C)
for (int c=0; c<n; c++) n*n*(C+(n+1)*C+n*C)
sum += a*b*c; n*n*n
return sum; C
}

Runs in cubic time O(n3)

The number of elementary steps is ~ n3
Complexity Examples (4)

long SumMN(int n, int m)

{
long sum = 0;
for (int x=0; x<n; x++)
for (int y=0; y<m; y++)
sum += x*y;
return sum;
}

Runs in quadratic time O(n*m)

The number of elementary steps is ~ n*m
Complexity Examples (5)
decimal Factorial(int n)
{
if (n==0)
return 1;
else
return n * Factorial(n-1);
}

T(n) = c + c + T(n-1)
T(n) = 2c + 2c + T(n-2)
T(n) = 2c+ 2c + 2c + T(n-3) = 3 2c + T(n-3)
After ith substutition: T(n)= i 2c + T(n-i)
if i=n then: T(n)= n 2c + 1 => O(n)

Runs in linear time O(n)

The number of elementary steps is ~ n
Complexity Examples (6)
decimal Fibonacci(int n)
{
if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}

T(n) = T(n-1) + T(n-2) < T(n-1) + T(n-1)

= 2*T(n-1) = 2*2*T(n-2) = 2*2*2*T(n-3) .... = 2^i*T(n-i)

... ==> O(2^n)

Runs in exponential time O(2n)