Algorithm Analysis
CS 201
Introduction
● Once a correct algorithm is designed for a given problem, an important step is
to determine how much in the way of resources (such as time and space) the
algorithm will require.
You will learn how to estimate the time required by the algorithm.
● The idea is not to find the exact computational time required by the algorithm
since this time is to be affected by other factors.
○ The programming language using which it is implemented
○ The machine on which it is run
● Instead, we want to identify how the required time for the algorithm grows as a
function of its input size.
You will learn asymptotic notations to express the growth rate of the algorithm.
2
Introduction
● To analyze algorithms:
○ First, we will start counting the number of significant operations in a particular solution to
assess its efficiency.
○ Then, we will express the efficiency of algorithms using growth functions.
● We will employ mathematical techniques that analyze algorithms
independently of specific implementations, computers, or data.
3
How to find the time complexity of a given program?
● 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).
○ Although different instructions can take different amounts of time, one may ignore this
difference in the analysis.
● Obviously, we cannot have this assumption for complex operations such as
matrix inversion, list insertion, and sorting.
● We assume infinite memory.
● We do not include the time required to read the input.
4
General rules
Rule 1 – loop: The running time of a loop is at most the running time of the
statements inside the 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 number of iterations performed by all of the
loops.
Rule 3 – if / else: The running time is never more than that of the test plus the
larger of the running times of S1 and S2.
if ( test )
S1
else
S2
Rule 4 – consecutive statements: Just add their running times. 5
Example
Consecutive statements
Times
count = count + 1; 1
sum = sum + count; 1
Total cost = 1 + 1
→ The time required for this algorithm is constant
Don’t forget: We assume that each simple operation takes one unit of time
6
Example
If-else statements
Times
if (n < 0){ 1
absval = -n 1
cout << absval; 1
}
else
absval = n; 1
Total Cost ≤ 1 + max(2,1)
7
Example
Single loop statements
Times
i = 1; 1
sum = 0; 1
while (i <= n) { n+1
i = i + 1; n
sum = sum + i; n
}
Total cost = 1 + 1 + (n + 1) + n + n
→ The time required for this algorithm is proportional to n
8
Example
Nested loop statements Times
i = 1; 1
sum = 0; 1
while (i <= n) { n+1
j=1; n
while (j <= n) { n * (n+1)
sum = sum + i; n*n
j = j + 1; n*n
}
i = i + 1; n
}
Total cost = 1 + 1 + (n + 1) + n + n * (n + 1) + n * n + n * n + n
→ The time required for this algorithm is proportional to n2 9
Mathematical background
● We measure the time requirement of an algorithm as a function of problem size.
● The most important thing is to learn how quickly the time requirement of an
algorithm grows as a function of the problem size.
● Asymptotic notations are used to express the growth rate of a function.
● They allow to establish a relative order among functions.
● You will learn three asymptotic notations: big-Oh, big-omega, big-theta.
Compare f(n) = n, g(n) = 1000 n and h(n) = n2
● We do not want to claim that g(n) < h(n)
○ Since you can find points for which g(n) is less than h(n) and vice versa
● Instead, we want to compare their relative rates of growth as a function of n
○ The growth rates of f(n) and g(n) are the same
○ The growth rates of both of these functions are less than that of h(n)
10
Asymptotic notations: Big-Oh
● This notation is used to express an upper-bound on a function.
● T(n) = O( f(n) )
○ f(n) is an upper-bound on T(n).
○ The growth rate of T(n) is less than or equal to that of f(n).
○ T(n) grows at a rate no faster than f(n).
Definition (Big-Oh)
T(n) = O( f(n) ) if there exist positive constants c and n0 such that 0 ≤ T(n) ≤ c f(n) for all n ≥ n0.
As an exercise, show that
○ 2 n2 = O( n2 ) → n2 is an upper-bound on 2 n2
○ 100 n2 = O( n3 ) → n3 is an upper-bound on 100 n2
○ n2 ≠ O( 10000 n ) → But 10000 n is not an upper-bound on n2
11
Example
Show that 2n2 = O(n3)
We need to find two positive constants: c and n0 such that:
0 ≤ 2n2 ≤ cn3 for all n ≥ n0
Choose c = 2 and n0 = 1
→ 2n2 ≤ 2n3 for all n ≥ 1
Or, choose c = 1 and n0 = 2
→ 2n2 ≤ n3 for all n ≥ 2
12
Example
Show that 2n2 + n = O(n2)
We need to find two positive constants: c and n0 such that:
0 ≤ 2n2 + n ≤ cn2 for all n ≥ n0
2 + (1/n) ≤ c for all n ≥ n0
Choose c = 3 and n0 = 1
→ 2n2 + n ≤ 3n2 for all n ≥ 1
13
Asymptotic notations: Big-omega
● This notation is used to express a lower-bound on a function.
● T(n) = Ω( g(n) )
○ g(n) is a lower-bound on T(n).
○ The growth rate of T(n) is greater than or equal to that of g(n).
○ T(n) grows at a rate no slower than g(n).
Definition (Big-omega)
T(n) = Ω( g(n) ) if there exist positive constants c and n0 such that 0 ≤ c f(n) ≤ T(n) for all n ≥ n0.
As an exercise, show that
○ 2 n2 = Ω( n2 ) → n2 is also a lower-bound on 2 n2
○ 100 n2 = Ω( n ) → n is a lower-bound on 100 n2
○ n ≠ Ω( n2 ) → But n2 is not a lower-bound on n
14
Asymptotic notations: Big-theta
● This notation is used to express a tight-bound on a function.
● T(n) = Θ( h(n) )
○ h(n) is a tight-bound on T(n).
○ The growth rate of T(n) is equal to that of h(n).
Definition (Big-theta)
T(n) = Θ( h(n) ) if and only if T(n) = O( h(n) ) and T(n) = Ω( h(n) ).
○ n2 = O( n3 ) but n2 ≠ Ω( n3 ) → n2 grows slower than n3, thus n2 ≠ Θ( n3 )
○ n3 ≠ O( n2 ) but n3 = Ω( n2 ) → n3 grows faster than n2, thus n3 ≠ Θ( n2 )
○ 2 n2 = O( n2 ) and 2 n2 = Ω( n2 ) → 2 n2 and n2 grows at the same rate,
and thus, 2 n2 = Θ( n2 )
15
Big-Oh notation
c1 f(n)
c f(n)
T(n) T(n)
T(n) c f(n) c2 f(n)
O(f(n)) Ω(f(n)) Θ(f(n))
Big-O definition implies: constant n0 beyond which it is satisfied.
We do not care about small values of n.
Asymptotic running times of
algorithms are usually defined by
functions whose domain are
n={0, 1, 2, …} (natural numbers) 16
Asymptotic notations
Rule 1: If T1(n) = O( f(n) ) and T2(n) = O( g(n) )
○ T1(n) + T2(n) = O( f(n) + g(n) )
○ T1(n) x T2(n) = O( f(n) x g(n) )
Rule 2: If T(n) is a polynomial of degree k, then T(n) = Θ( nk ).
Rule 3: logm (n) = O( n ) for any constant m → Logarithms grow very slowly!
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.
If h( n ) = 2n2 + 100n
Do NOT say h(n) = O( 2n2 + 100n ) or h(n) = O( 2n2 ) or h(n) = O( n2 + n ).
The correct form is h(n) = O( n2 ).
17
Typical growth rates
Function Name
c Constant
log n Logarithmic
log2 n Log-squared
n Linear
n log n
n2 Quadratic
n3 Cubic
2n Exponential
18
A comparison of growth-rate functions
19
A comparison of growth-rate functions
● Any algorithm with n! complexity is useless for n ≥ 20.
● Algorithms with 2n running time is impractical for n ≥ 40.
● Algorithms with n2 running time is usable up to n = 10,000.
○ But not useful for n > 1,000,000
● Linear time (n) and n log n algorithms remain practical even for one billion
items.
● Algorithms with log n complexity is practical for any value of n.
20
Algorithm analysis
● If two programs are expected to take similar times, probably the best way to
decide which is faster is to code them both up and run them!
● On the other hand, we would like to eliminate the bad algorithmic ideas early
by algorithm analysis.
○ Asymptotic notations are not affected by the programming language. Thus, there is no need
to code an algorithm for finding its time complexity (you can analyze the time complexity of
even a pseudocode). However, after coding the algorithm, if it runs much more slowly than
the algorithm analysis suggests, there may be an implementation inefficiency.
Although using big-theta would be more precise, big-Oh answers are typically given.
21
Simple example: What is the time complexity of the following function?
int partialSumOfSquares( int* arr, int n ){
int result = 0;
for ( int i = 0; i < n; i++ )
if ( arr[ i ] < 0)
result += arr[i] * arr[i];
return result;
}
22
More examples: What are the time complexities of the following code fragments?
➔ for ( i = 0; i < n * n; i++ ) ➔ for ( i = 1; i < n; i *= 2 )
k++; k++;
➔ for ( i = 0; i < n * n; i += 40 ) ➔ for ( i = n; i > 10; i /= 4 )
k++; k++;
➔ for ( i = 0; i < n * n; i += n ) ➔ for ( i = 0; i < n / 100; i++ )
k++; for ( j = m; j > 40; j -= 4 )
k++;
➔ for ( i = 10; i < n * n / 3; i += 2 ) ➔ for ( i = 1; i < n; i *= 5 )
k++; for ( j = m / 2; j < m; j++ )
k++;
➔ for ( i = 0; i < 1000000000; i++ )
k++;
23
General rules
Rule 5 – function calls: Find the running time of each function call. Be careful
about their analyses if these are recursive functions. The analysis is trivial
for some recursions, but could be hard for some others.
long factorial( int n ) { Recurrence relation:
if ( n <= 1 ) T(n) = T(n - 1) + Θ(1)
return 1; T(1) = Θ(1)
Solving it with repeated substitutions:
return n * factorial(n - 1); T(n) = T(n - 1) + Θ(1)
} T(n) = T(n - 2) + Θ(1) + Θ(1)
T(n) = T(n - 3) + Θ(1) + Θ(1) + Θ(1)
...
T(n) = T(n - k) + k Θ(1)
T(n) = T(1) + (n - 1) Θ(1)
T(n) = n Θ(1)
T(n) = Θ(n)
24
Example: What is the time complexity of the Hanoi tower algorithm?
void hanoi(int n, char source, char dest, char spare) {
if (n > 0) {
hanoi(n - 1, source, spare, dest);
move from source to dest
hanoi(n - 1, spare, dest, source);
} Recurrence relation:
} T(n) = 2 T(n - 1) + Θ(1)
T(0) = Θ(1)
Solving it with repeated substitutions:
T(n) = 2 [2 T(n - 2) + Θ(1)] + Θ(1)
T(n) = 2 [2 [2 T(n - 3) + Θ(1)] + Θ(1) + Θ(1)
... k-1
= 2 T(n - k) + ∑ 2i Θ(1)
k
i=0
... n-1
= 2n T(n - n) + ∑ 2i Θ(1)
i=0
= 2n T(0) + [2n - 1] Θ(1)
= Θ(2n) 25
Some useful mathematical equalities
26
Example: What is the time complexity of the following power functions?
long iterativePower( long x, long n ) {
long result = 1;
for ( int i = 1; i <= n; i++ )
result = result * x;
return result;
}
long recursivePower( long x, long n ) { Recurrence relation:
if ( n == 0 ) T(n) = T(n / 2) + Θ(1)
return 1; T(1) = Θ(1)
if ( n == 1 )
Solving it with repeated substitutions:
return x;
T(n) = T(n / 2) + Θ(1)
if ( n % 2 == 0 )
T(n) = T(n / 4) + Θ(1) + Θ(1)
return recursivePower( x * x, n / 2 ); T(n) = T(n / 8) + Θ(1) + Θ(1) + Θ(1)
...
return recursivePower( x * x, n / 2) * x; T(n) = T(n / 2k) + k Θ(1)
} T(n) = T(1) + log n Θ(1)
T(n) = Θ(1) + Θ(log n)
T(n) = Θ(log n)
27
Example: What is the time complexity of the following Fibonacci functions?
int iterativeFib( int n ) {
int previous = 1, current = 1, next = 1;
for ( int i = 3; i <= n; i++ ) {
next = current + previous;
previous = current;
current = next;
}
return next;
}
int recursiveFib( int n ) { Recurrence relation:
if ( n <= 2 )
return 1;
T(n) = T(n - 1) + T(n - 2) + Θ(1)
return recursiveFib(n - 1) + recursiveFib(n - 2); T(1) = Θ(1)
}
By induction, it is possible to show that
T (n) < ( 5 / 3 )n and
T (n) ≥ ( 3 / 2 )n
Thus, the running time of recursiveFib
grows exponentially !!!
28
Worst-case, best-case, and average-case analyses
● Typically, the input size is the main consideration.
● Sometimes, the input size to be considered may differ from one run to another.
○ Worst-case analysis represents a guarantee on any possible input.
○ Best-case analysis is often of little interest.
○ Average-case analysis often reflects the typical behavior.
■ It is valid if you can figure out what the “average” input is.
■ It is computed considering all possible inputs and their probability distribution.
● Generally, we focus on the worst-case analysis.
○ It provides a bound on all inputs.
○ Average-case bounds are much more difficult to compute.
29
Example: Find the worst case, best case, and average case upper-bounds for
the sequential search algorithm.
int sequentialSearch( int* arr, int n, int value ){
for ( int i = 0; i < n; i++)
if ( arr[i] == value )
return i;
return -1;
}
● For a successful search:
○ Best-case: Only 1 iteration is necessary when the value is the first array item → O( 1 )
○ Worst-case: n iterations are necessary when the value is the last array item → O( n )
○ Average-case: (n + 1) / 2 iterations are necessary on the average.
For calculating this average, one needs to consider all possibilities → O( n )
● For an unsuccessful search:
○ Worst-case, best-case, and average-case are all the same → O( n )
30
Example: Find the worst case, best case, and average case upper-bounds
for the binary search algorithm.
int binarySearch( int* arr, int n, int value ){
int low = 0, high = n - 1;
while ( low <= high ) {
int mid = (low + high) / 2;
if ( arr[ mid ] < value )
low = mid + 1;
else if ( arr[ mid ] > value )
high = mid - 1;
else
return mid;
} 0 1 2 3 4 5 6 7 ← an array with size 8
return -1; 3 2 3 1 3 2 3 4 ← # of iterations
} The average # of iterations = 21/8 < log28
● For a successful search:
○ Best-case: The number iterations is 1 → O( 1 )
○ Worst-case: The number iterations is ⎣log2n⎦ +1 → O( log n )
○ Average-case: The average number of iterations < log2n → O( log n )
● For an unsuccessful search:
○ Worst-case, best-case, and average-case are all the same → O( log n ) 31
Problem of the day
32
Problem of the day
33
Problem of the day
34
Problem of the day
T
F
T
35
Problem of the day
36
Problem of the day
T
F
T
F
37
Problem of the day
T
F
T
F
T
38
Problem of the day
39
Problem of the day
T
F
T
F
T
T
40
Problem of the day
41
Problem of the day
T
F
T
F
T
T
F
42