Algorithm Analysis

1
Outline
• Comparing algorithms

• Pseudocode

• Theoretical Analysis of Running time

• Primitive Operations
• Counting primitive operations

• Asymptotic analysis of running time

2
 Algorithm
What is an algorithm?
• An algorithm is any well-defined computational procedure that takes
some value, or set of values, as input and produces some value, or
set of values, as output.

• An algorithm is thus a sequence of computational steps that

transform the input into the output.

• An algorithm is a finite set of instructions that, if followed,

accomplishes a particular task.

• An algorithm is a finite set of precise instructions for performing a

computation or for solving a problem. 3
Properties of algorithms:
•Input Zero or more quantities externally supplied

•Output At least one quantity is produced

• Definiteness Each instruction is clear and unambiguous

•Finiteness If we trace out the instructions of an algorithm, then for all

cases, the algorithm terminates after a finite number of steps

• Effectiveness Every instruction must be very basic so that it can be

carried out, in principle, by a person using only pencil and paper. It is
not enough that each operation be definite as in criterion 3; it also
must be feasible
4
Areas of Algorithm study
• How to devise algorithms? –Creating an algorithm is an art which may never
be fully automated

• How to validate algorithm? Once an algorithm is devised, it is necessary to

show that it computes the correct answer for all possible legal inputs.

• How to analyze algorithms? Analysis of algorithms or performance analysis

refers to the task of determining how much computing time and storage an
algorithm requires

• How to test a program? Testing a program consists of two phases:

• Debugging is the process of executing programs on sample data sets to determine
whether faulty results occur and, if so, to correct them

• Profiling or performance measurement is the process of executing a correct program

on datasets and measuring the time and space it takes to compute the result 5
 Pseudocode
• In this course, we will mostly use Example: find max element of an
pseudocode to describe an array
algorithm
Algorithm arrayMax(A, n)
• Pseudocode is a high-level Input: array A of n integers
description of an algorithm Output: maximum element of A

• More structured than English currentMax  A[0]

prose for i  1 to n  1 do

• Less detailed than a program if A[i]  currentMax then

currentMax  A[i]
• Preferred notation for describing
return currentMax
algorithms

• Hides program design issues

6
 Pseudocode Details
• Control flow

• if … then … [else …]

• while … do … Algorithm arrayMax(A, n)

Input: array A of n integers
• repeat … until …
Output: maximum element of A
• for … do …
currentMax  A[0]
• Indentation replaces braces for i  1 to n  1 do
if A[i]  currentMax then
• Method declaration
currentMax  A[i]
Algorithm method (arg, arg…) return currentMax

Input …

Output … 7
Pseudocode Details
• Method call
method (arg [, arg…]) Algorithm arrayMax(A, n)

• Return value Input: array A of n integers

Output: maximum element of A
return expression
currentMax  A[0]
• Expressions
for i  1 to n  1 do
 Assignment
if A[i]  currentMax then
(like  in Java)
currentMax  A[i]
 Equality testing
return currentMax
(like  in Java)
n2 superscripts and other
mathematical formatting
allowed 8
 Comparing Algorithms
• Given 2 or more algorithms to solve the same problem, how do we
select the best one?

• Some criteria for selecting an algorithm

 Is it easy to implement, understand, modify?
 How long does it take to run it to completion?
 How much of computer memory does it use?

• Software engineering is primarily concerned with the first criteria

• In this course we are interested in the second and third criteria

9
 Comparing Algorithms
• Time complexity

o The amount of time that an algorithm needs to run to completion

• Space complexity

o The amount of memory an algorithm needs to run

• We will occasionally look at space complexity, but we are

mostly interested in time complexity in this course

• Thus in this course the better algorithm is the one which runs

faster (has smaller time complexity)

10
Theoretical Analysis of Running Time

• Uses a pseudo-code description of the algorithm instead of an

implementation

• Characterizes running time as a function of the input size, n

• Takes into account all possible inputs

• Allows us to evaluate the speed of an algorithm independent of the

hardware/software environment

11
Primitive Operations
For theoretical analysis, we will count primitive or basic operations,
which are simple computations performed by an algorithm
• Basic operations are:
• Identifiable in pseudocode Examples:
Evaluating an expression
• Largely independent from the
Assigning a value to a
programming language variable
• Exact definition not important Indexing into an array

(we will see why later) Calling a method

• Instructions have to be basic Returning from a method

enough and feasible!

• Assumed to take a constant

amount of time
12
Primitive Operations

• Examples of primitive operations:

• Evaluating an expression x2+ey
• Assigning a value to a variable cnt  cnt+1
• Indexing into an array A[5]
• Calling a method mySort(A,n)
• Returning from a method return(cnt)

13
How to Calculate Running time

• Most algorithms transform input objects into output objects

sorting
5 3 1 2 1 2 3 5
algorithm
input object output object

• The running time of an algorithm typically grows with the input

size
 Idea: analyze running time as a function of input size

14
How to Calculate Running Time

• Even on inputs of the same size, running time can be very

different
• Example: algorithm that finds the first prime number in an array
by scanning it left to right

• Idea: analyze running time in the

 best case

 worst case

 average case
15
How to Calculate Running Time
• Best case running time is
usually useless best case
average case
worst case
• Average case time is very 120

useful but often difficult to 100

Running Time
80
determine
60

• We focus on the worst case 40

20
running time
0
• Easier to analyze 1000 2000 3000 4000
Input Size
• Crucial to applications such as
games, finance and robotics
16
Experimental Evaluation of Running Time
• Write a program implementing
9000
the algorithm
8000

• Run the program with inputs of 7000

6000
varying size and composition

Time (ms)
5000

• Use a method like 4000

3000
[Link]() to get an 2000

accurate measure of the actual 1000

0
running time 0 50 100
Input Size
• Plot the results
17
Limitations of Experiments
• Experimental evaluation of running time is very useful but
• It is necessary to implement the algorithm, which may be difficult
• Results may not be indicative of the running time on other inputs
not included in the experiment
• In order to compare two algorithms, the same hardware and
software environments must be used

18
Counting Primitive Operations
• By inspecting the pseudocode, we can determine the maximum number of
primitive operations executed by an algorithm, as a function of the input size

Algorithm arrayMax(A, n) # operations

currentMax  A[0] 2

for i  1 to n  1 do 2+n

if A[i]  currentMax then 2(n  1)

currentMax  A[i] 2(n  1)

{ increment counter i } 2(n  1)

return currentMax 1

Total 7n  1
19
 Estimating Running Time
• Algorithm arrayMax executes 7n  1 primitive operations in the worst
case.

• Define:
a = Time taken by the fastest primitive operation
b = Time taken by the slowest primitive operation

• Let T(n) be worst-case time of arrayMax. Then

a (7n  1)  T(n)  b(7n  1)

• Hence, the running time T(n) is bounded by two linear functions

20
Growth Rate of Running Time
• Changing the hardware/software environment
Affects T(n) by a constant factor, but
Does not alter the growth rate of T(n)

• Thus we focus on the big-picture which is the growth rate

of an algorithm
• The linear growth rate of the running time T(n) is an
intrinsic property of algorithm arrayMax
• algorithm arrayMax grows proportionally with n, with its true
running time being n times a constant factor that depends on the
specific computer 21
Constant Factors
• The growth rate is not affected by
• Constant factors or
• lower-order terms

• Examples
• 102n + 105 is a linear function
• 105n2 + 108n is a quadratic function

• How do we get rid of the constant factors to focus on

the essential part of the running time?

22
Big-Oh Notation

• Or asymptotic analysis
The big-Oh notation is used widely to characterize running
times and space bounds
The big-Oh notation allows us to ignore constant factors and
lower order terms and focus on the main components of a
function which affect its growth

23
Big-Oh Notation Definition
• Given functions f(n) and g(n),
80
we say that f(n) is O(g(n)) if
70 3n
there are positive constants 60 2n+10

c and n0 such that 50

n
40
f(n)  cg(n) for n  n0 30
20
• Example: 2n + 10 is O(n) 10

• 2n + 10  cn 0
0 5 10 15 20 25 30
• (c  2) n  10 n
• n  10/(c  2)

• Pick c  3 and n0  10
24
Big-Oh Example

• Example: the function n2 1,00,000

n^2
90,000
100n
is not O(n) 80,000 10n
• n2  cn 70,000 n
60,000
• nc
50,000
• The above inequality 40,000
cannot be satisfied since c 30,000
20,000
must be a constant
10,000
0
0 100 200 300 400 500
n

25
More Big-Oh Examples
 7n-2
7n-2 is O(n)
need c > 0 and n0  1 such that 7n-2  c•n for n  n0
this is true for c = 7 and n0 = 1

 3n3 + 20n2 + 5
3n3 + 20n2 + 5 is O(n3)
need c > 0 and n0  1 such that 3n3 + 20n2 + 5  c•n3 for n  n0
this is true for c = 4 and n0 = 21

 3 log n + 5
3 log n + 5 is O(log n)
need c > 0 and n0  1 such that 3 log n + 5  c•log n for n  n0
this is true for c = 8 and n0 = 3

26
Big-Oh and Growth Rate
• The big-Oh notation gives an upper bound on the growth rate of a
function
• The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no
more than the growth rate of g(n)
• We can use the big-Oh notation to rank functions according to their
growth rate

f(n) is O(g(n)) g(n) is O(f(n))

g(n) grows more Yes No
f(n) grows more No Yes
Same growth Yes Yes

27
Big-Oh Rules

f n  a0 + a1n + a2 n + ... + ad n

2 d

• If is f(n) a polynomial of degree d, then f(n) is O(nd), i.e.,

• Drop lower-order terms
• Drop constant factors

• Use the smallest possible class of functions

• Say “2n is O(n)” instead of “2n is O(n2)”

• Use the simplest expression of the class

• Say “3n + 5 is O(n)” instead of “3n + 5 is O(3n)”
28
Asymptotic Algorithm Analysis
• The asymptotic analysis of an algorithm determines the running time in big-
Oh notation
• To perform the asymptotic analysis
• We find the worst-case number of primitive operations executed as a
function of the input size
• We express this function with big-Oh notation
• Example:
• We determine that algorithm arrayMax executes at most 7n  1
primitive operations
• We say that algorithm arrayMax “runs in O(n) time”
• Since constant factors and lower-order terms are eventually dropped any
how, we can disregard them when counting primitive operations
29
Important Functions
• Often appear in algorithm analysis:
• Constant  1
• Logarithmic  log n
• Linear  n
• N-Log-N  n log n
• Quadratic  n2
• Cubic  n3
• Exponential  2n

30
 Important Functions Growth Rates

n log(n) n nlog(n) n2 n3 2n
8 3 8 24 64 512 256

16 4 16 64 256 4096 65536

32 5 32 160 1024 32768 4.3x109

64 6 64 384 4096 262144 1.8x1019

128 7 128 896 16384 2097152 3.4x1038

256 8 256 2048 65536 16777218 1.2x1077

31
Growth Rate Illustration
Assume that a computer executes a million instructions a second.
This chart summarizes the amount of time required to execute f(n)
instructions on this machine for various values of n.

f(n) n=103 n=105 n=106

log2(n) 10-5 sec 1.7 * 10-5 sec 2 * 10-5 sec
n 10-3 sec 0.1 sec 1 sec
n*log2(n) 0.01 sec 1.7 sec 20 sec
n2 1 sec 3 hr 12 days
n3 17 min 32 yr 317 centuries
2n 10285 centuries 1010000 years 10100000 years

32
Useful Big-Oh Rules
• If is f(n) a polynomial of degree d, then f(n) is O(nd)

 If d(n) is O(f(n)) and e(n) is O(g(n)) then

 d(n)+e(n) is O(f(n)+g(n))

 d(n)e(n) is O(f(n) g(n))

 If d(n) is O(f(n)) and f(n) is O(g(n)) then d(n) is O(g(n))

 If p(n) is a polynomial in n then log p(n) is O(log(n))

33
Computing Prefix Averages
• We further illustrate asymptotic
analysis with two algorithms for
35
prefix averages X
30 A
• The i-th prefix average of an array X 25
is average of the first (i + 1) 20
elements of X: 15
10
A[i]  X[0] + X[1] + … + X[i])/(i+1)
5

• Computing the array A of prefix 0

1 2 3 4 5 6 7
averages of another array X has
applications to financial analysis
34
 Prefix Averages (Quadratic)
 The following algorithm computes prefix averages in
quadratic time by applying the definition

Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X
#operations
A  new array of n integers n
for i  0 to n  1 do n
s0 n
for j  0 to i do 1 + 2 + …+ (n  1)
s  s + X[j] 1 + 2 + …+ (n  1)
A[i]  s / (i + 1) n
return A 1
35
 Arithmetic Progression
• The running time of prefixAverages1 is
O(1 + 2 + …+ n)

• The sum of the first n integers is

n(n + 1) / 2

• Thus, algorithm prefixAverages1 runs in O(n2) time

36
Prefix Averages (Linear)
 The following algorithm computes prefix averages in
linear time by keeping a running sum
Algorithm prefixAverages2(X, n)
Input array X of n integers
Output array A of prefix averages of X
#operations
A  new array of n integers n
s0 1
for i  0 to n  1 do n
s  s + X[i] n
A[i]  s / (i + 1) n
return A 1

 Algorithm prefixAverages2 runs in O(n) time

37
 More Examples
Algorithm SumTripleArray(X, n)
Input triple array X[ ][ ][ ] of n by n by n integers
Output sum of elements of X #operations
s0 1
for i  0 to n  1 do n
for j  0 to n  1 do n+n+…+n=n2
for k  0 to n  1 do n2+n2+…+n2 = n3
s  s + X[i][j][k] n2+n2+…+n2 = n3
return s 1

 Algorithm SumTripleArray runs in O(n3) time

38
 Relatives of Big-Oh
 big-Omega

f(n) is (g(n)) if there is a constant c > 0

and an integer constant n0  1 such that

f(n)  c•g(n) for n  n0

 big-Theta

f(n) is (g(n)) if there are constants c’ > 0 and c’’ > 0

and an integer constant n0  1 such that

c’•g(n)  f(n)  c’’•g(n) for n  n0

39
 Intuition for Asymptotic Notation
Big-Oh

 f(n) is O(g(n)) if f(n) is asymptotically less than or equal to

g(n)

big-Omega

 f(n) is (g(n)) if f(n) is asymptotically greater than or

equal to g(n)

 Note that f(n) is (g(n)) if and only if g(n) is O(f(n))

big-Theta

 f(n) is (g(n)) if f(n) is asymptotically equal to g(n)

 Note that f(n) is (g(n)) if and only if if g(n) is O(f(n)) and

if f(n) is O(g(n)) 40
Example Uses of the Relatives of Big-Oh
 5n2 is (n2)
f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0  1
such that f(n)  c•g(n) for n  n0
let c = 5 and n0 = 1
 5n2 is (n)
f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0  1
such that f(n)  c•g(n) for n  n0
let c = 1 and n0 = 1
 5n2 is (n2)
f(n) is (g(n)) if it is (n2) and O(n2). We have already seen the former,
for the latter recall that f(n) is O(g(n)) if there is a constant c > 0 and an
integer constant n0  1 such that f(n) < c•g(n) for n  n0
Let c = 5 and n0 = 1

41
Analysis in General

We want an easily recognized elementary function to

describe the performance of the algorithm, so we
use the dominant term of T(n): it determines the
basic shape of the function

42
Analysis in General

To determine the time complexity of an algorithm:

• Express the amount of work done as a sum
f1(n) + f2(n) + … + fk(n)
• Identify the dominant term: the fj such that fj is
O(g(n)) and for k different from j
fk (n) < fj (n) (for all sufficiently large n)
• Then the time complexity is O(g(n))
43
 Analysis in General
• Examples of dominant terms:
n dominates log2(n)
n*log2(n) dominates n
n2 dominates n*log2(n)
nm dominates nk when m > k
an dominates nm for any a > 1 and m >= 0

• That is, log2(n) < n < n*log2(n) < n2 < … < nm < an for a >= 1 and m > 2

44
Analysis in General
• With independent nested loops: The number of iterations of the
inner loop is independent of the number of iterations of the outer
loop

• Example:

int x = 0; Outer loop executes n/2 times.

for ( int j = 1; j <= n/2; j++ ) For each of those times, inner

for ( int k = 1; k <= n*n; k++ ) loop executes n2 times, so the

x = x + j + k; body of the inner loop is

executed (n/2)*n2 = n3/2 times.
The algorithm is O(n3) .
45
Analysis in General

With dependent nested loops: Number of iterations of the inner loop

depends on a value from the outer loop

• Example: When j is 1, inner loop executes 3

times; when j is 2, inner loop executes

int x = 0; 3*2 times; … when j is n, inner loop

for ( int j = 1; j <= n; j++ ) executes 3*n times.

for ( int k = 1; k < 3*j; k++ ) In all the inner loop executes
x = x + j; 3+6+9+…+3n = 3(1+2+3+…+n)

= 3n2/2 + 3n/2 times.

The algorithm is O(n2).

46
Mathematics Review
 Summations

 Logarithms and Exponents

• properties of logarithms:
logb(xy) = logbx + logby
logb (x/y) = logbx - logby
logbxa = alogbx
logba = logxa/logxb
• properties of exponentials:
a(b+c) = aba c
abc = (ab)c
ab /ac = a(b-c)
b = a logab
bc = a c*logab

47
Sum of First n Natural Numbers
Write down the terms of the sum in forward and reverse orders; there are n
terms:
T(n) = 1 + 2 + 3 + … + (n-2) + (n-1) + n
T(n) = n + (n-1) + (n-2) + … + 3 + 2 +1
Add the terms in the boxes to get:
2*T(n) = (n+1) + (n+1) + (n+1) + … + (n+1) + (n+1) + (n+1)
= n(n+1)
Therefore, T(n) = (n*(n+1))/2 = n2/2 + n/2

48
 Final Notes
Running time
 Even though in this course we focus on
the asymptotic growth using big-Oh A
notation, practitioners do care about
constant factors occasionally
B
 Suppose we have 2 algorithms

 Algorithm A has running time 30000n 10000

 Algorithm B has running time 3n2 problem size

 Asymptotically, algorithm A is better than

algorithm B

 However, if the problem size you deal

with is always less than 10000, then the
49
quadratic one is faster
Intractable problems

• A problem is said to be intractable if solving it by computer is

impractical

• Example: Algorithms with time complexity O(2n) take too

long to solve even for moderate values of n; a machine that
executes 100 million instructions per second can execute 260
instructions in about 365 years

50
 Constant Time Complexity

• Algorithms whose solutions are independent of the size of the

problem’s inputs are said to have constant time complexity

• Constant time complexity is denoted as O(1)

51