CHAPTER 4:

ALGORITHM ANALYSIS TOOLS

1

Prof. Mohamad Kassab

FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
2
THE CONSTANT FUNCTION
▪ This function is defined as:

Number of operations
f(n) = c
▪ The most fundamental constant
function is:
g(n) = 1
▪ Any other constant function,
f(n) = c, can be written as a constant
constant c times g(n):
n (input size)
f (n) = cg(n)
▪ For basic operations, e.g., addition or an assignment, the required number
of operations is constant, i.e., independent of the size of the input, n.
▪ E.g., x = 5; takes the same time as x = 5296681223;
▪ E.g., y = 5+6; takes the same time as y = 5296681220 + 6800741180; 3
 CODE Run “Constant Function” file
DEMONSTRATION
4
FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
5
THE LOGARITHM FUNCTION
▪ This function is defined as:
f(n) = x = logb n if bx = n

Number of operations
b is the base of the logarithm
Example:
▪ Given f(n) = log2 n, we have:
➢ f(8) = 3 (because 23 = 8) logarithmic
➢ f(16) = 4 (because 24 = 16) constant
➢ f(32) = 5 (because 25 = 32)
n (input size)
➢ f(64) = 6 (because 26 = 64)

▪ The most common base used in computer science is 2. Thus, by convention:

log(n) = log2(n) 6
 THE LOGARITHM RULES
▪ There are some important rules for logarithms. Given real
numbers a > 0, b > 1, c > 0 and d > 1, we have:

rule 1.
rule 2.
rule 3.
rule 4.
rule 5.

7
 CODE Run “Logarithmic Function”

DEMONSTRATION file

8
FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
9
THE LINEAR FUNCTION
▪ This function is defined as:
f(n) = n

Number of operations
▪ E.g., comparing a number k to
each element of an array of size linear

n requires n comparisons.
▪ This function represents the best logarithmic
runtime we can hope to achieve constant
when performing n iterations:
for(int i=0; i<n; i++){ n (input size)
// code goes here...
}
10
 CODE 1- Run “Linear Function” file
2- Modify number of

DEMONSTRATION iterations and observe the

time

11
FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
12
THE N-LOG-N FUNCTION
▪ This function is defined as:

Number of operations
f(n) = n log n
n log n
linear

logarithmic
constant

n (input size)

13
FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
14
THE QUADRATIC FUNCTION
▪ This function is defined as:
quadratic

Number of operations
f(n) = n2
n log n
▪ This function represents the best linear
runtime we can hope to achieve
when performing 𝑛 × 𝑛 iterations:
for(int i=0; i<n; i++){ logarithmic
for(int j=0; j<n; j++){ constant
//code goes here...
} n (input size)
}
15
THE QUADRATIC FUNCTION
▪ This function is defined as:
f(n) = n2
▪ This function represents the best What about this nested loop,
runtime we can hope to achieve which is also commonly used
when performing n x n iterations: in computer science?
for(int i=0; i<n; i++){ for(int i=0; i<n; i++){
for(int j=0; j<n; j++){ for(int j=0; j<i; j++){
//code goes here... //code goes here...
} }
} }
16
THE QUADRATIC FUNCTION
▪ Number of performed iterations:
𝑛
𝑛(𝑛 + 1)
1+2+3+⋯+𝑛 = ෍𝑥 =
2
𝑥=1
What about this nested loop,
▪ This is not too far from n2 which is also commonly used
in computer science?
▪ Thus, the best runtime we can
for(int i=0; i<n; i++){
hope to achieve by performing
for(int j=0; j<i; j++){
these iterations can also be //code goes here...
considered to be quadratic! }
}
17
 CODE 1- Run “Quadratic Function” file
2- Modify number of iterations and observe the
DEMONSTRATION time

18
FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
19
THE CUBIC FUNCTION
▪ This function is defined as: cubic
quadratic

Number of operations
f(n) = n3
n log n
▪ This represents the best runtime linear
we can hope to achieve when
performing 𝑛 × 𝑛 × 𝑛 iterations:
for(int i=0; i<n; i++){ logarithmic
for(int j=0; j<n; j++){ constant
for(int k=0; k<n; k++){
//code goes here... n (input size)
}
}
20
POLYNOMIALS
▪ A polynomial function is a function of the form
𝑑

𝑓 𝑛 = 𝑎0 + 𝑎1 𝑛 + 𝑎2 𝑛2 + 𝑎3 𝑛3 + ⋯ + 𝑎𝑑 𝑛𝑑 = ෍ 𝑎𝑖𝑛𝑖
𝑖=0

o Coefficients: a0 , a1 , . . . , ad are constants

o Degree of the polynomial: Integer d, which

indicates the highest power in the polynomial.
21
POLYNOMIALS
▪ Examples of polynomial functions:
o f(n) = 2 + 5n + n2

o f(n) = 1 + n3

o f(n) = 1
o f(n) = n

o f(n) = n2

▪ Thus, all the functions we mentioned so far are polynomials.

22
FUNCTIONS FOR THE ANALYSIS OF
ALGORITHMS
1. The Constant Function
2. The Logarithm Function
3. The Linear Function
4. The N-Log-N Function
5. The Quadratic Function
6. The Cubic Function and Other Polynomials
7. The Exponential Function
23
THE EXPONENTIAL FUNCTION
▪ This function is defined as: exponential cubic
quadratic

Number of operations
f(n) = bn
n log n
o Base: b is a positive constant
linear
o Exponent: n

▪ In algorithm analysis, the most

common base is b = 2 logarithmic
constant

n (input size)

24
THE EXPONENTIAL FUNCTION
▪ Exponent rules:

𝑏𝑎 𝑐 = 𝑏 𝑎×𝑐 e.g. 256 = 162 = (24)2 = 24x2 = 28 = 256

𝑏𝑎𝑏𝑐 = 𝑏 𝑎+𝑐 e.g. 243 = 35 = 32+3 = 3233 = 9x27 = 243

𝑏𝑎
= 𝑏 𝑎−𝑏 e.g. 16 = 1024/64 = 210/26 = 210−6 = 24 = 16
𝑏𝑐
𝑛
𝑎 𝑛+1 − 1
e.g. 1 + 2 + 4 + 8 + 16 + . . . + 2n-1 = 2n - 1
෍ 𝑎𝑖 =
𝑎−1
𝑖=0
25
 CODE 1- Run “Exponential Function” file
2- Modify number of iterations and observe the
DEMONSTRATION time

26
COMPARING GROWTH RATES
exponential
▪ The difference between
cubic
the functions is huge,
especially if n is large! quadratic

n log n

linear

logarithmic

27
COMPARING GROWTH RATES
exponential
▪ The difference between
cubic
the functions is huge,
especially if n is large! quadratic

blue = instantaneous;

green = fast; n log n

yellow = caution; linear

logarithmic
red = super slow!

28
COMPARING GROWTH RATES

blue = instantaneous; green = fast; yellow = caution; red = super slow!

29
ANALYSIS OF ALGORITHMS
▪ Factors impacting the running time:
o Input size
o Hardware environment (processor, memory, etc.)
o Software environment (e.g. operating system,
programming language, compiler, interpreter, etc.)
▪ We will focus on the relationship between the running
time of an algorithm and the size of its input
30
EXPERIMENTAL STUDIES
▪ One way to evaluate runtime
is to test one algorithm on
various inputs, and plot the

Time in milliseconds
runtime against input size
➢ Note that the input instances
might vary in runtime even if
they have the same size!
➢ This is because the input
instances may vary in other
attributes apart from the size.
input size
31
EXPERIMENTAL STUDIES
▪ While experimental studies of runtime are useful, they have 3 limitations:

➢ Experiments can only be done on a limited set of test inputs (e.g., we

cannot test billions of input instances if this would require years of
runtime)

➢ It is hard to compare two algorithms unless the experiments were

performed in the same hardware and software environments.

➢ We must implement the algorithm in order to study its running time

experimentally.

32
THEORETICAL STUDIES
▪ To avoid the limitations of experimental studies, we can analyze the
runtime mathematically. This method:
➢ takes into account all possible input instances

➢ allows us to evaluate the relative efficiency of any two algorithms in a

way that is independent from hardware and software.
➢ can be performed by studying a high-level description of the algorithm
without actually implementing it or running experiments on it.
▪ This methodology aims at associating, with each algorithm, a function
f(n) that characterizes the running time of the algorithm as a function
of the input size n. Typically, f(n) is one of the 7 functions we have seen.
33
COUNTING PRIMITIVE OPERATIONS
▪ Theoretical analysis involves counting “primitive” operations:

➢ Assigning a value to a variable

➢ Comparing two numbers
➢ An arithmetic operation (e.g., adding two numbers)
➢ Calling a function
➢ Indexing into an array
➢ Following an object reference
➢ Returning from a function
Usually, theoretical analysis tends to focus on the first three.
34
 FOCUSING ON THE AVERAGE CASE
▪ Theoretical analysis may express the runtime as a function of the input size by taking
the average over all possible inputs of the same size.

▪ Unfortunately, such an
average-case analysis is

Time in milliseconds
typically challenging, as it
requires us to calculate the
expected runtime based on
a given input distribution,
which usually involves
sophisticated probability
theory.

▪ Let’s see an example…

input size 35
 FOCUSING ON THE AVERAGE CASE
Example: what is the average ▪ The if-statement is performed n times for any A
number of primitive operations? ▪ The number of assignments of max depends on A

Given this A, the number of assignments = 1:

Algorithm Max( A, n )
10 10 10 10 10 10 10 10 10 10 10 10
Input: An array A of n integers
max ← A[0]
Given this A, the number of assignments = n:
for i ←1 to n-1 do
if max < A[i] then 10 20 30 40 50 60 70 80 90 100 110 120

max ← A[i-1]
Given this A, the number of assignments = n /2:
As can be seen, even for this very 10 10 10 10 10 10 10 80 90 100 110 120
simple algorithm, it is not easy to
Given this A, the number of assignments = n /2:
figure out the average number
10 20 10 40 10 60 10 80 10 100 10 10
over all possible inputs!
36
 FOCUSING ON THE WORST CASE
What if we focus our analysis on the worst case? What would be the number of primitive
operations for this algorithm?
▪ Our analysis can focus on constructing a
single input instance that requires the
Algorithm Max( A, n )
largest number of primitive operations
Input: An array A of n integers
max ← A[0] ▪ For this algorithm, the worst case is to
for i ←1 to n-1 do have an input like this one, which would
if max < A[i] then
require n assignments:
max ← A[i-1]
10 20 30 40 50 60 70 80 90 100 110 120

▪ What about the primitive operations in the line ( for i

←1 to n-1 do )? This performs
about n comparisons and n assignments. Thus, the total number of operations is:
(2 n operations in the for loop) + (n if-statements) + (n assignments of max) = 4n
37
 FOCUSING ON THE WORST CASE
▪ Worst-case analysis requires identifying the worst-case input, which is often simple

▪ Thus, we characterize runtime

in terms of the worst case!
Moreover, when designing an

Time in milliseconds
algorithm, we tend to focus
on improving its performance
given the worst possible input

▪ The idea is: If an algorithm

performs well on the worst
input, it performs well on all
inputs!
input size 38
 WHAT MATTERS IS THE GROWTH RATE
▪ In computer science, we focus
exponential
on classifying algorithms into
cubic
broad categories, e.g., when
the input size increases, how quadratic
does the runtime grow?
➢ linearly?
➢ logarithmically?
n log n
➢ polynomial?
➢ exponentially? linear

logarithmic
▪ We’ve seen an algorithm that
requires 4 n in the worst case
but if we want to look at the big picture, it doesn’t matter much if it is 4 n or 20 n or
even 1000 n; what matters the most is that it’s linear!
39
40
ASYMPTOTIC NOTATION
THE “BIG-OH” NOTATION
▪ We say that c𝑔(𝑛)

f(n) is O(g(n))
𝑓(𝑛)
which is pronounced as follows:
“f(n) is big-Oh of g(n)”
if there exists a constant c > 0 and
an integer n0 ≥ 1 such that:
𝑛0 𝑛
f(n) ≤ cg(n), for n ≥ n0

41
THE “BIG-OH” NOTATION
Example: Prove that 8n−2 is O(n). c𝑔(𝑛)
Justification:
𝑓(𝑛)
▪ f(n) = 8n-2, g(n) = n, and we need to find
c > 0 and n0 > 1 such that:
f(n) ≤ cg(n), for n ≥ n0

▪ we need to find c > 0 and n0 ≥ 1 such that

8n−2 ≤ cn, for n ≥ n0 𝑛0 𝑛
▪ A possible choice is c = 8 and n0 = 1, because:
8n − 2 ≤ 8n, for n ≥ 1
42
THE “BIG-OH” NOTATION
Example: If f(n) is a polynomial of degree d, i.e.,
c𝑔(𝑛)
f(n) = a0 + a1n + ··· + adnd
and ad > 0, then: f(n) is O(nd)
𝑓(𝑛)
Justification: we need to find c > 0 and n0 > 1
such that:
f(n) ≤ cg(n), for n ≥ n0
▪ We know that the following holds for n ≥ 1:
1 ≤ n ≤ n2 ≤ ··· ≤ nd
▪ Thus, for n0 > 1: 𝑛0 𝑛
a0 + a1n + a2n2 + ··· + adnd ≤ (a0+a1+a2+···+ad) nd See the other
f(n) c g(n) examples in the
book!
▪ Hence, it suffices to set c = a0+a1+ ··· +ad and n0 =1 43
WHY DO WE USE THE “BIG-OH”
▪ The big-Oh notation is used widely to characterize running
times and space bounds in terms of some parameter n,
which varies from problem to problem, but is always defined
as a chosen measure of the “size” of the problem

▪ It allows us to ignore constant factors and lower order terms

and focus on the main components of a function that affect
its growth, i.e. the “order” of the function.

44
THE “BIG-OH” - EXAMPLES
What is the growth rate in big-oh notation for each of these
functions? (Try to do it intuitively, without a formal proof)
▪ 5n2 + 3n log n + 2n + 5 O(n2)

▪ 20n3 + 10n log n + 5 O(n3)

▪ 3 log n + 2 O(log n)
▪ 2n+2 O(2n)

▪ 2n + 100 log n O(n)

45
THE “BIG-OH” - CONVENTION
▪ While it is true that the function f(n) = 4n3 +3n2 is O(n5) or even O(n4), it is
more accurate to say that it is O(n3).

▪ It is also considered poor taste to include constant factors and lower order
terms in the big-Oh notation.
▪ E.g., although this is completely correct to say that 2n2 is O(4n2 +6nlog n),
we should strive to describe the function in the big-Oh in simplest terms

▪ The seven functions that we’ve seen are the most commonly used:
▪ E.g., An algorithm that runs in worst-case time 4n2 +n log n is said to be a
quadratic-time algorithm, since it runs in O(n2) time.
▪ An algorithm running in time at most 5n+20 log n+4 would be called a
linear-time algorithm. 46
 HIDING THE CONSTANT
▪ As we said, our goal is to classify algorithms
into broad categories based on the rate at
which runtime grows with n, e.g., O(n), O(n2), …
Example:
▪ Whether the runtime is 3n, or 5n, or 15n, it is
still a linear algorithm. Thus, we do not write
O(15n), but rather O(n)
▪ It is as if we are saying “regardless of the constant, this is a linear algorithm,
i.e., it is O(n), and the constant does not change the fact that its runtime grows
at a rate slower than that of an O(n log n) algorithm”
▪ Thus, the big-Oh notation “hides” the constant and focuses on growth rate.
47
 HIDING THE CONSTANT
▪ Example: If an algorithm requires 10100n
operations, then after hiding the constant
10100, the runtime is O(n). Thus:
✓ It must be fast, right?
✓ It must be faster than O(n log n), right?
✓ It must be much faster than O(n2), right?

No!
▪ Note that 106 is a million; 109 is a billion; 1012 is a trillion; 10100 is greater than
the number of atoms in the universe!
▪ It is true that 10100n will eventually grow at a slower rate than n2, but this will
only occur when n is very, very, very large!
▪ Thus, big-Oh provide broad guidelines, but be aware of the hidden constant! 48
 WHAT IS AN “EFFICIENT” ALGORITHM?
▪ What is an efficient algorithm?

▪ If we must draw a line between efficient

and inefficient algorithms, then this line is
often considered to fall between algorithms
running in polynomial time and those
running in exponential time.

49
 WHAT IS AN “EFFICIENT” ALGORITHM?
▪ What is an efficient algorithm?

▪ If we must draw a line between efficient

and inefficient algorithms, then this line is
often considered to fall between algorithms
running in polynomial time and those
running in exponential time.

▪ But be careful! An algorithm running in

O(n1000) time should probably not be considered “efficient”!

▪ Nevertheless, the distinction between polynomial-time and exponential-time

algorithms is a robust measure of tractability in general.
50
 EXAMPLE – PREFIX AVERAGE
▪ Given an array, X, of n elements, design an algorithm that returns an array, A,
such that:
A[i] equals the average of the elements X[0], X[1], …, X[i]
▪ Here is a potential algorithm. What is the complexity?

No. of executions: n O(n)

𝑛 𝑛+1
No. of executions: (1+2+3+…+n) =
2
O(n2)
No. of executions: n O(n)

▪ Thus, runtime is a polynomial of degree 2, which is O(n2) 51

 EXAMPLE – PREFIX AVERAGE
▪ The prefix average problem is defined as follows: Given an array, X, of n
elements, design an algorithm that returns an array, A, such that:
A[i] equals the average of the elements X[0], X[1], …, X[i]
▪ However, one can develop an alternative algorithm by exploiting the similarity
between A[i-1] and A[i]:
A[i-1] = (X[0] + X[1] + … + X[i-1]) / i
A[i] = (X[0] + X[1] + … + X[i-1] + X[i]) / (i+1)
▪ Thus, if we use a temporary variable, s, that is computed for every i as follows:
s = (X[0] + X[1] + … + X[i-1])
we can compute A[i] as follows:
A[i] = s + X[i] / (i+1)
52
 EXAMPLE – PREFIX AVERAGE
▪ The prefix average problem is defined as follows: Given an array, X, of n
elements, design an algorithm that returns an array, A, such that:
A[i] equals the average of the elements X[0], X[1], …, X[i]
▪ Here is the new algorithm. What is the complexity?

No. of executions: 1 O(1)

No. of executions: n O(n)

No. of executions: n O(n)

▪ Thus, it runs in O(n) time, which is much faster than the previous algorithm!
53