Algorithm analysis

• Reasons to analyze algorithms?

Subject: Introduction to Algorithm
• Correctness
Lecturer: Hoang Do Thanh Tung • Running time

Credit points 3 ECTS • How to estimate the running time

Level Undergraduate • Mathematical Background
Teaching time 2021
• What to analyze?
Location University of Science and Technology of Hanoi
• How to analyse?
• Exercises
Write down this algorithm
Input: b, n
Process:
Output: bn
Your algorithm….
Variable n, b, rs;
Get n, b from user; - Start the program
Set rs=1; - Create a variable named b,n
For (I = 1 to n): rs=rs*b; - Get the value of b and n from the user
Print(rs); - Create a variable named exponential
- Initialize exponential to 1
Input b,n - Create a variable named i to hold a counter from 1 to n
Start the program - Initialize i to 1
Set a variable to hold the result - Loop While i is less than or equal to n
Result = b power of n + multiply exponential by b
Print result + add 1 to i
End - Now repeat
- Print exponential
Smart power algorithm
 Idea: b1000 = b500  b500. If we know b500, we can compute b1000 with only 1
more multiplication!
 Smart power algorithm:
To compute bn:
Set p to 1, set q to b, and set m to n.
While m > 0
If m is odd, p= p . q.
m = m mod 2 (discarding any remainder).
q=q.q
Loop
Return p
Analysis

 Analysis (counting multiplications):

to perform at most 2 multiplications.
They are repeated as often as we must halve the value of n
(discarding any remainder) until it reaches 0, i.e., floor(log2 n) + 1
times.
Max. no. of multiplications = 2(floor(log2 n) + 1)
= 2 floor(log2 n) + 2

2-5
Compare two algorithms

 Comparison: 50
simple power
algorithm
40

30
multiplications
20
smart power
algorithm
10

0
0 10 20 30 40 50
2-6
n
After writing down an algorithm,
we also need to convince ourselves that

• the algorithm does what it’s supposed to do, and

• it does efficiently.
algorithm does what it’s supposed to
do = Correctness
Is an algorithm Correct?
 We must prove that
 Outputs are correct for all possible inputs
 Trusting our instincts, or trying a few test cases, isn’t good enough, even
fairly obvious
 ‘obvious’ is all too often a synonym for ‘wrong’

Inputs Processing Outputs

input: A sequence of numbers.

output: An ordered permutation of the input.
issues: correctness, efficiency, storage, etc.
is an algorithm Efficient?
Efficiency of an algorithm
 The algorithm is “best” of given several algorithms to solve the same
problem
 The “best” is
 is it efficient enough to be usable in practice?
 fastest running time to process
 lowest space (memory) to use
 In general, both time and space requirements depend on the
algorithm’s input (typically the “size” of the input).
Example: “running time” efficiency
 Hypothetical profile of two sorting algorithms:

4
Key:
3 Algorithm A
Algorithm B
time
2
(ms)

0
10 20 30 40 items to be sorted, n

• Algorithm B’s time grows more slowly than A’s.

Running Time – Definition

 Call each simple instruction and access to a word of memory a “primitive

operation” or “step.”
 Running time of an algorithm for a given input is
 The number of steps executed by the algorithm on that input.
 Often referred to as the complexity of the algorithm.
Complexity and Input

 Complexity of an algorithm generally depends on

 Size of input.
 Input size depends on the problem.
 Examples: No. of items to be sorted.

 No. of vertices and edges in a graph.

 Other characteristics of the input data.

 Are the items already sorted?
 Are there cycles in the graph?
How to measure Efficiency?
 For a program, we measure time in seconds
 is useful in practice
 depends on language, compiler, disk access and processor..
 For an algorithm, we count algorithm steps?
 Is useful in theory and practice
 does not depend on compiler or processor, but only on the algorithm itself
 depends on granularity of operation steps.
How to estimate the running time
• Mathematical Background
• What to analyze?
• How to analyse?
• Exercises
Mathematical Background
Powers
 Consider a number b and a non-negative integer n.
Then b to the power of n (written bn) is the multiplication
of n copies of b:
bn = b  …  b
E.g.: b3 = bbb
b2 = bb
b1 = b
b0 = 1
Logarithms
 Consider a positive number y. Then the logarithm of y to the base 2
(written log2 y) is the number of copies of 2 that must be multiplied
together to equal y.
 If y is a power of 2, log2 y is an integer: since 20 = 1
E.g.: log2 1 = 0
since 21 = 2
log2 2 = 1
log2 4 = 2 since 22 = 4
log2 8 = 3
since 23 = 8

• If y is not a power of 2, log2 y is fractional:

E.g.: log2 5  2.32
log2 7  2.81
Logarithm laws

 log2 (2n) = n
 log2 (xy) = log2 x + log2 y
 log2 (x/y) = log2 x – log2 y
Logarithms example (1)
 How many times must we halve the value of n (discarding any
remainders) to reach 1?
 Suppose that n is a power of 2:
E.g.: 8421 (8 must be halved 3 times)
16  8  4  2  1 (16 must be halved 4 times)
If n = 2m, n must be halved m times.
 Suppose that n is not a power of 2:
E.g.: 9421 (9 must be halved 3 times)
15  7  3  1 (15 must be halved 3 times)
If 2m < n < 2m+1, n must be halved m times.
Logarithms example (2)
 In general, n must be halved m times if:
2m  n < 2m+1
i.e., log2 (2m)  log2 n < log2 (2m+1)
i.e., m  log2 n < m+1
i.e., m = floor(log2 n).
 The floor of x (written floor(x) or x) is the largest integer not greater than
x.
 Conclusion: n must be halved floor(log2n) times to reach 1.
 Also: n must be halved floor(log2n)+1 times to reach 0.

2-22
How to compare two functions?

 The idea of the following definitions is to establish a relative order among

functions.
 Given two functions, there are usually points where one function is smaller than
the other function.
 It does not make sense to claim f(N) < g(N)
 Let us compare f(N) = 1000N and g(N) = N2
 Thus, we will compare their relative rates of growth
Mathematical background

 Definition 1:
f ( N ) = O( g ( N ))
if there are positive constants c and n0 such that
f ( N )  c  g ( N ) when N  n0

 Meaning:

f ( N ) = O( g ( N )) means that
the growth rate of f ( N ) is less than or equal to that of g ( N )
Because
f ( N ) grows at a rate no faster than g ( N ), Thus g ( N ) is an upper bound on f ( N )
Mathematical background

 Definition 2:
f ( N ) = ( g ( N )) if there are positive constants c and n0
such that f ( N )  c  g ( N ) when N  n0

 Meaning
f ( N ) = ( g ( N )) says that the growth rate of f ( N ) is
greater than or equal to that of g ( N )
− f ( N ) grows at a rate no slower than g ( N )
− Thus g ( N ) is a lower bound on f ( N )
Mathematical background

 Definition 3:
asymptotic
f ( N ) = ( g ( N )) if and only if
f ( N ) = O( g ( N )) and f ( N ) = ( g ( N ))

 Meaning

f ( N ) = ( g ( N )) says that the growth rate of f ( N )

equals to that of g ( N )
Examples
 f(N)=N3 grows faster than g(N)=N2, so
g(N) = O(f(N)) or f(N) = (g(N))

 f(N)=N2 and g(N)=2N2 grow at the same rate, so

f(N) = O(g(N)) and f(N) = (g(N))

 If g(N)=2N2, g(N)=O(N4), g(N)=O(N3), g(N)=O(N2) are

all technically correct, but the last one is the best
answer.

 Do not say T(N)=O(2N2) or T(N)=O(N2+N). The

correct form is T(N)=O(N2).
Mathematical background

 Rule 1: If T1 ( N ) = O( f ( N )) and T2 ( N ) = O( g ( N )), then

(a) T1 ( N ) + T2 ( N ) = O( f ( N ) + g ( N ))
(b) T1 ( N )  T2 ( N ) = O( f ( N )  g ( N ))

If T ( N ) is a polynomial of degree k , then

 Rule 2:
T ( N ) = ( N ) k

log k N = O( N ) for any constant k .

 Rule 3:
This tells us that logarithms grow very slowly.
Examples
 Determine which of f(N)=N logN and g(N)=N1.5
grows faster.
→ Determine which of logN and N0.5 grows faster.

→ Determine which of log2N and N grows faster.

→ Since N grows faster than any power of a log,

g(N) grows faster than f(N).
Growing rate of log n - n

 Comparison: 50
n

40

30

20

10
log n

0
0 10 20 30 40 50
n
Examples
 Consider the problem of downloading a file over the
Internet.
 Setting
up the connection: 3 seconds
 Download speed: 1.5 Kbytes/second
 If a file is N kilobytes, the time to download is T(N)
= N/1.5 + 3, i.e., T(N) = O(N).
 1500K file takes 1003 seconds
 750K file takes 503 seconds
 If the connection speed doubles, both times
decrease, but downloading 1500K still takes
approximately twice the time downloading 750K.
y = x2 + 3x + 5, for x=1..10

32
y = x2 + 3x + 5, for x=1..20

33
How to find O(g(N))?
Simply :
1- dismiss lower powers (keep only the highest power)
2- Replace the highest power coefficient with a constant (c )

Ex: y=4x4+8x3+10x2+14x+17
Y <= c. x4, so c?
What will be the notations?
O (n) Ω (n) ∂(n)
O (n4) Ω (n4) ∂(n4)

So what are the difference between them ?

Value of constant and n0

e.x) f (n)= 4n4 + 8n3+-10n2+14n +17

c.g(n)= c(n4)
f (n)= 4n4 + 8n3+-10n2+14n +17≤ CN4
ASSUM N0=1 THEN:
4+8-10+14+17 ≤ c so 33 ≤ c
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 = 2
O-notation

 Common time complexities:

O(1) constant time (feasible)
O(log n) logarithmic time (feasible)
O(n) linear time (feasible)
O(n log n) log linear time (feasible)
O(n2) quadratic time (sometimes feasible)
O(n3) cubic time (sometimes feasible)
O(2n) exponential time (rarely feasible)
Common time complexities
BETTER  O(1) constant time
 O(log n) log time
 O(n) linear time
 O(n log n) log linear time
 O(n2) quadratic time
 O(n3) cubic time
 O(nk) polynomial time

n
O(2 ) exponential time

WORSE
Growth rates

 Comparison of growth rates:

1 1 1 1 1
log n 3.3 4.3 4.9 5.3
n 10 20 30 40
n log n 33 86 147 213
n2 100 400 900 1,600
n3 1,000 8,000 27,000 64,000
2n 1,024 1.0 million 1.1 billion 1.1 trillion
Growth rates (2)
 Graphically: 100
2n n2 n log n

80

60
n
40

20
log n

0
0 10 20 30 40 50
n
Plots of various algorithms
Comparison of Algorithms

 Complexity function can be used to compare the

performance of algorithms.
 Algorithm A is more efficient than Algorithm B for solving a
problem, if the complexity function of A is of lower order
than that of B.
 Examples:
 Linear Search – (n) vs. Binary Search – (lg n)
 Insertion Sort – (n2) vs. Quick Sort – (n lg n)
What to Analyze?
We analyze algorithms, not programs
 The most important resource to analyze is generally
the running time
 We assume that simple instructions (such as addition,
comparison, and assignment) take exactly one unit time
 Unlike the case with real computers
 For example, I/O operations take more time compared to comparison
and arithmetic operators
 Obviously,we do not have this assumption for fancy
operations such as matrix inversion, list insertion, and
sorting.
 We assume infinite memory
 We do not include the time required to read the input
Running Time – Definition

 Call each simple instruction and access to a word of

memory a “primitive operation” or “step.”
 Running time of an algorithm for a given input is
 The number of steps executed by the algorithm on
that input.
 Often referred to as the complexity of the algorithm.
Complexity and Input
 Complexity of an algorithm generally depends on
 Size of input.
 Input size depends on the problem.
 Examples: No. of items to be sorted.
 No. of vertices and edges in a graph.
 Other characteristics of the input data.
 Are the items already sorted?
 Are there cycles in the graph?
What does “size of the input” mean?

 If we are searching an array, the “size” of the input could be the size of the array
 If we are merging two arrays, the “size” could be the sum of the two array sizes
 If we are computing the nth Fibonacci number, or the nth factorial, the “size” is n
 We choose the “size” to be a parameter that determines the actual time (or space)
required
 It is usually obvious what this parameter is
 Sometimes we need two or more parameters
Sorting
• insertion sort: (n2)
• merge sort: (n lg n)
Comparisons For a sequence of 106 numbers,
of Algorithms • the insertion sort took 5.56 hrs on a
supercomputer using machine
language;
• the merge sort took 16.67 min on a PC
using C/C++.
Worst-case Complexity

• Maximum steps the algorithm takes for any possible

input.
Worst, • Most tractable measure.

Average, and Average-case Complexity

• Average of the running times of all possible inputs.

Best-case • Demands a definition of probability of each input,
which is usually difficult to provide and to analyze.

Complexity Best-case Complexity

• Minimum number of steps for any possible input.

• Not a useful measure. Why?
Big-0 typically used in Algorithm analysis

 Although using Big-Theta would be more precise, Big-O

answers are typically given.

 Big-O answer is not affected by the programming

language
 If a program is running much more slowly than the algorithm
analysis suggests, there may be an implementation inefficiency
 e.g., This can occur in C++ when arrays are inadvertently copied in
their entirety instead of passed with references.
Algorithm analysis assumption
 If two programs are expected to take similar times,
probably the best way to decide which is faster to
 code them both up and
 run them
 So, Algorithm analysis is to eliminate the bad
algorithmic ideas early before coding
 Although different instructions can take different amounts of
time, we ignore this difference
Examples…
A Simple Example – Linear Search
INPUT: a sequence of n numbers, key to search for.
OUTPUT: true if key occurs in the sequence, false otherwise.
LinearSearch(A, key) cost times
1 i1 c1 1
2 while i ≤ n and A[i] != key c2 x

n
3 do i++ c3 x-1 i =2
1

4 if i  n c4 1
5 then return true c5 1
6 else return false c6 1
x ranges between 1 and n+1.
So, the running time ranges between
c1+ c2+ c4 + c5 – best case
and
c1+ c2(n+1)+ c3n + c4 + c6 – worst case
A Simple Example – Linear Search
INPUT: a sequence of n numbers, key to search for.
OUTPUT: true if key occurs in the sequence, false otherwise.

LinearSearch(A, key) cost times

1 i1 1 1
2 while i ≤ n and A[i] != key 1 x

n

3 do i++ 1 x-1 i =2
1

4 if i  n 1 1
5 then return true 1 1
6 else return false 1 1

Assign a cost of 1 to all statement executions.

Now, the running time ranges between
1+ 1+ 1 + 1 = 4 – best case
and
1+ (n+1)+ n + 1 + 1 = 2n+4 – worst case
A Simple Example – Linear Search
INPUT: a sequence of n numbers, key to search for.
OUTPUT: true if key occurs in the sequence, false otherwise.
LinearSearch(A, key) cost times
1 i1 1 1
2 while i ≤ n and A[i] != key 1 x

n
3 do i++ 1 x-1 i =2
1

4 if i  n 1 1
5 then return true 1 1
6 else return false 1 1

If we assume that we search for a random item in the list,

on average, Statements 2 and 3 will be executed n/2 times.
Running times of other statements are independent of input.
Hence, average-case complexity is
1+ n/2+ n/2 + 1 + 1 = n+3
How to analyse algorithmes
Running Time

 Number of primitive steps that are executed

 Except for time of executing a function call most statements roughly require
the same amount of time

Method Cost
A=1 1
B=A+1 3
C=A*B 4
D=A+B+C 6
EXAMPLE

Method Cost
A=0 1
FOR I =1 to 3 3
A= A + i
Constant time
 Constant time means there is some constant k such that a
operation always takes k nanoseconds
 A operation
 does not include a loop
 does not include calling a method whose time is unknown or is
not a constant
 If a statement involves a choice (if or switch) among
operations, each of which takes constant time
 This is consistent with worst-case analysis
Linear time
 We may not be able to predict to the nanosecond, but do
know complexity about timing
for (i = 0, j = 1; i < n; i++) {
j = j * i;
}
 This loop takes time k*n + c, for some constants k and c
k : How long it takes to go through the loop once
(the time for j = j * i, plus loop overhead)
n : The number of times through the loop
(we can use this as the “size” of the problem)
c : The time it takes to initialize the loop
 The total time k*n + c is linear in n
Constant time is (usually)
better than linear time
 Suppose we have two algorithms to solve a task:
 Algorithm A takes 5000 time units
 Algorithm B takes 100*n time units
 Which is better?
 Clearly, algorithm B is better if our problem size is small, that is, if
n < 50
 Algorithm A is better for larger problems, with n > 50
 So B is better on small problems that are quick anyway
 But A is better for large problems, where it matters more
 We usually care most about very large problems
 But not always!
What about the constants?
 An added constant, f(n)+c, becomes less and less
important as n gets larger
 A constant multiplier, k*f(n), does not get less important,
but...
 Improving k gives a linear speedup (cutting k in half cuts
the time required in half)
 Improving k is usually accomplished by careful code
optimization, not by better algorithms
 We aren’t that concerned with only linear speedups!
 Bottom line: Forget the constants!
Analyse a simple example

 int sum( int n )

{ Count:
int partialSum; • Lines 1 and 4 = 1 + 1 = 2
• Line 3 = 4 x n
1 partialSum = 0; • Line 2 = 1 + (n + 1) + n = 2n + 2
2 for( int i = 1; i <= n; ++i ) Total = 6n + 4
3 partialSum += i * i * i;
4 return partialSum;
}

If we had to perform all this work to analyze any algorithm, we would quickly become crazy.
in terms of Big-Oh
• line 3 is obviously an O(1) statement (per execution)
• Line 1, 4 is constant, so it is silly to waste time here
Simplifying the formulae
 Throwing out the constants is one of two things we do in
analysis of algorithms
 By throwing out constants, we simplify 12n2 + 35 to
just n2
 Our timing formula is a polynomial, and may have terms of
various orders (constant, linear, quadratic, cubic, etc.)
 We usually discard all but the highest-order term
 We simplify n2 + 3n + 5 to just n2
Big O notation

 When we have a polynomial that describes the time requirements of an

algorithm, we simplify it by:
 Throwing out all but the highest-order term
 Throwing out all the constants
 If an algorithm takes 12n3+4n2+8n+35 time, we simplify this formula to
just n3
 We say the algorithm requires O(n3) time
 We call this Big O notation
 Later on we will talk about related Big  and Big θ
Can we justify Big O notation?
 Big O notation is a huge simplification; can we
justify it?
 It only makes sense for large problem sizes
 For sufficiently large problem sizes, the
highest-order term swamps all the rest!
 Consider R = x2 + 3x + 5 as x varies:
x=0 x2 = 0 3x = 0 5=5 R=5
x = 10 x2 = 100 3x = 30 5=5 R = 135
x = 100 x2 = 10000 3x = 300 5=5 R = 10,305
x = 1000 x2 = 1000000 3x = 3000 5=5 R = 1,003,005
x = 10,000 x2 = 108 3x = 3*104 5 = 5 R = 100,030,005
x = 100,000 x2 = 1010 3x = 3*105 5 = 5 R = 10,000,300,005
General rules
 Rule 1 – for loops: The running time of a for loop is at
most the running time of the statements inside the for
loop (including tests) times the number of iterations

 Rule 2 – nested loops: Analyze these inside out. The

total running time of a statement inside a group of
nested loops is the running time of the statement
multiplied by the product of the sizes of all the loops

for (i = 0; i < n; i++)

for (j = i; j < n; j++)
k++;
Analyzing Code
 Nested loops

for i = 1 to n do
for j = 1 to n do
sum = sum + 1

n n
T ( n) =   1= n = n Number_of_iterations
n 2
j =1 * time_per_iteration
i =1 i =1
Analyzing Code
 Nested loops

for i = 1 to n do
for j = i to n do
sum = sum + 1
n n n n n
T ( n) =  1 =  (n − i + 1) =  (n + 1) −  i
i =1 j =i i =1 i =1 i =1

n(n + 1) n(n + 1)
= n(n + 1) − = = ( n )
2

2 2
Exercise
 A more complicated example

for ( i=0; i<=n; i++)

for ( j=i; j>=1; j= j/5 )
sum = sum + 1

T(n) = ?
General rules
 Rule 3 – consecutive statements: just add.
for (i = 0; i < n; i++)
a[i] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i] += a[j] + i + j;

 Rule 4 – if/else: For the following, the running time is

never more than that of the test plus the larger of that
of S1 and S2
if (condition)
S1
else
S2
Analyzing Code

 Conditional statements
if C then S1 else S2
time  time(C) + Max( time(S1), time(S2))

 Loops
for i  a1 to a2 do S

time   time(Si) for all i

Example running time for loop

For loop Running time

for ( i = 0; i < n; i++ ) n

for ( i = 0; i < n; i++ ) n*n = n^2
for j = 0; j < n; j++ )

Int I = 0 1
Int sum = 0 1
For 0 to 50
51
Example
 Alg.: MIN (a[1], …, a[n])
m ← a[1];
for i ← 2 to n
if a[i] < m
then m ← a[i];
 Running time:
T(n) =1 [first step] + (n) [for loop] + (n-1) [if condition] +
(n-1) [the assignment in then] = 3n - 1
 T(n) grows like n
Recursive functions
 If there are function calls, these must
be analyzed first
 If there are recursive functions, be
careful about their analyses. For some
recursions, the analysis is trivial
long factorial(int n){
if (n <= 1)
return 1;
return n * factorial(n-1);
}
 T(n) = T(n — 1) + 3
T(0) = 1
 T(n) = T(n-1) + 3
= T(n-2) + 6
= T(n-3) + 9
= T(n-4) + 12

Recursive
= ...
= T(n-k) + 3k

running time  as we know T(0) = 1

we need to find the value of k for which n - k =
0, k = n
 T(n) = T(0) + 3n , k = n
= 1 + 3n
 that gives us a time complexity of O(n)
Recursive functions
 Let us analyze the following recursion
long fib(int n){
if (n <= 1)
return 1;
return fib(n-1) + fib(n-2);
}
T ( N ) = T ( N −1) + T ( N − 2) + 2

 By induction, it is possible to show that
fib( N )  (5 / 3) N and fib( N )  (3 / 2) N

 So the running time grows exponentially. By using a for loop,

the running time can be reduced substantially