Analysis of Algorithms
Data Structures and Algorithm Analysis in C, by Mark Allen Weiss, 2nd
edition, 1997, Addison-Wesley, ISBN 0-201-49840-5
Danang University of Science and Technology
Dang Thien Binh
dtbinh@[Link]
Readings and References
Reading
Chapter 2, Data Structures and Algorithm Analysis in C, Weiss
Other References
Data Structures 2
Asymptotic Behavior
The “asymptotic” performance as N → , regardle
ss of what happens for small input sizes N, is gene
rally most important
Performance for small input sizes may matter in pr
actice, if you are sure that small N will be common
forever
We will compare algorithms based on how they sc
ale for large values of N
Data Structures 3
Big-Oh Notation
The growth rate of the time or space required in relatio
n to the size of the input N is generally the critical issue
T(N) is said to be O(f(N)) if
there are positive constants c and n0 such that T(N) cf(N) for
N n0 .
ie, f(N) is an upper bound on T(N) for N n0
T(N) is “big-oh” of f(N) or "order" f(N)
Data Structures 4
x = 1:10;
y1 = x.*x;
y2 = 2*(x.*x)+x+1;
y3 = 3*(x.*x);
plot(x,y1,'r')
hold on
plot(x,y2,'g')
plot(x,y3,'b')
T(x) = 2x2 + x + 1 is O(x2)
Big-Oh Notation
Suppose T(N) = 50N
T(N) = O(N)
Take c = 50 and n0 = 1
Suppose T(N) = 50N+11
T(N) = O(N)
T(N) 50N+11N = 61N for N 1. So, c = 61 and n0 = 1 wo
rks
Data Structures 6
The common comparisons
Name Big-Oh
Constant O(1)
Log log O(log log N)
Increasing cost
Logarithmic O(log N)
Log squared O((log N)2)
}
Linear O(N)
N log N O(N log N)
Polynomial time
Quadratic O(N2)
Cubic O(N3)
Exponential O(2N)
Data Structures 7
n = 1:100;
y1 = n-n+1;
y2 = log2(n);
y3 = n;
y4 = n.*log2(n);
y5 = n.^2;
y6 = 2.^n;
from bigo.m
Exponential Growth swamps everything else
Bounds
Upper bound (O) is not the only bound of interest
Big-Oh (O), Little-Oh (o), Omega (), and Theta ():
(Fraternities of functions…)
Examples of time and space efficiency analysis
Data Structures 9
Big-Oh Notation
TA(N) = O(N2)
N2
TA(N) is O(N2)
because 50N N2
TA(N) = 50N for N 50.
So N2 is an upper
bound. But it's not a
very tight upper
bound.
Input Size N
Data Structures 10
Big-Oh and Omega
T(N) = O(f(N)) if there are positive constants c and n0 suc
h that T(N) cf(N) for N n0.
O(f(N)) is an upper bound for T(N)
100 log N, N0.9, 0.0001 N, 2100 N + log N are O(N)
T(N) = (f(N)) if there are positive constants c and n0 suc
h that T(N) cf(N) for N n0.
(f(N)) is a lower bound for T(N)
2N, Nlog N, N1.2, 0.0001 N, N + log N are (N)
Data Structures 11
Theta and Little-Oh
T(N) = (f(N)) iff T(N) = O(f(N)) and T(N) = (f(N))
(f(N)) is a tight bound, upper and lower
0.0001 N, 2100 N + log N are all = (N)
T(N) = o(f(N)) iff T(N) = O(f(N)) and T(N) (f(N))
f(N) grows faster than T(N)
100 log N, N0.9, sqrt(N), 17 are all = o(N)
Data Structures 12
For large N and ignoring constant f
actors
T(N) = O(f(N))
means T(N) is less than or equal to f(N)
Upper bound
T(N) = (f(N))
means T(N) is greater than or equal to f(N)
Lower bound
T(N) = (f(N))
means T(N) is equal to f(N)
“Tight” bound, same growth rate
T(N) = o(f(N))
means T(N) is strictly less than f(N)
Strict upper bound: f(N) grows faster than T(N)
Data Structures 13
Big-Oh Analysis of iterative sum function
Find the sum of the first num integers stored in array v.
Assume num size of v.
int sum ( int v[ ], int num) {
int temp_sum = 0, i; //1
for ( i = 0; i < num; i++ ) //2
temp_sum = temp_sum + v[i] ; //3
return temp_sum; //4
}
• lines 1, 3, and 4 take fixed (constant) amount of time
• line 2: i goes from 0 to num-1= num iterations
• Running time = constant + (num)*constant = O(num)
• Actually, (num) because there are no fast cases
Data Structures 14
Big-Oh Analysis of recursive sum function
Recursive function to find the sum of first num integers in v:
int sum ( int v[ ], int num){
if (num == 0) return 0; // constant time here
else return v[num-1] + sum(v,num-1); // constant + T(num-1)
}
• Let T(num) be the running time of sum
• Then, T(num) = constant + T(num-1)
• = 2*constant + T(num-2) =…= num*constant + constant
•= (num) (same as iterative algorithm!)
Data Structures 15
Common Recurrence Relations
Common recurrence relations in analysis of algorith
ms:
T(N) = T(N-1) + (1) T(N) = O(N)
T(N) = T(N-1) + (N) T(N) = O(N2)
T(N) = T(N/2) + (1) T(N) = O(log N)
T(N) = 2T(N/2) + (N) T(N) = O(N log N)
T(N) = 4T(N/2) + (N) T(N) = O(N2)
Data Structures 16
Big-Oh Analysis of Recursive Algorithm
s
To derive, expand the right side and count
Note: Multiplicative constants matter in recurrence r
elations:
T(N) = 4T(N/2) + (N) is O(N2), not
O(N log N)!
You will see these again later
you will only need to know a few specific relations and thei
r big-oh answers
Data Structures 17
Recursion
Recall the example using Fibonacci numbers
1, 1, 2, 3, 5, 8, 13, 21, 34, …
First two are defined to be 1
Rest are sum of preceding two
Leonardo Pisano
Fn = Fn-1 + Fn-2 (n > 1) Fibonacci (1170-1250)
Data Structures 18
Recursive Fibonacci Function
int fib(int N) {
if (N < 0) return 0; //invalid input
if (N == 0 || N == 1) return 1; //base cas
es
else return fib(N-1)+fib(N-2);
}
Running time T(N) = ?
Data Structures 19
Recursive Fibonacci Analysis
int fib(int N) {
if (N < 0) return 0; // time = 1 for (N < 0)
if (N == 0 || N == 1) return 1; // time = 3
else return fib(N-1)+fib(N-2); //T(N-1)+T(N-2)+1
}
Running time T(N) = T(N-1) + T(N-2) + 5
Using Fn = Fn-1 + Fn-2 we can show by inducti
on that T(N) FN. We can also show by induc
tion that FN (3/2)N
Therefore, T(N) (3/2)N
Exponential running time!
Data Structures 20
Iterative Fibonacci Function
int fib_iter(int N) {
int fib0 = 1, fib1 = 1, fibj = 1;
if (N < 0) return 0; //invalid input
for (int j = 2; j <= N; j++) { //all fib nos. up to N
fibj = fib0 + fib1;
fib0 = fib1;
fib1 = fibj;
}
return fibj;
}
Running time = ?
Data Structures 21
Iterative Fibonacci Analysis
int fib_iter(int N) {
int fib0 = 1, fib1 = 1, fibj = 1;
if (N < 0) return 0; //invalid input
for (int j = 2; j <= N; j++) { //all fib nos. up to N
fibj = fib0 + fib1;
fib0 = fib1;
fib1 = fibj;
}
return fibj;
}
Running time T(N) = constant+(N-1)•constant
T(N) = (N)
Exponentially faster than recursive Fibonacci
Data Structures 22
Appendix
Data Structures 23
Matlab - bigo.m
% bigO functions
% calculate and plot several functions used in comparing growth rates
figure
n = 1:100; % the x axis
y1 = n-n+1; % O(1)
y2 = log2(n); % O(log2(n))
y3 = n; % O(n)
y4 = n.*log2(n); % O(nlog2(n))
y5 = n.^2; % O(n^2)
y6 = 2.^n; % O(2^n)
plot(n,y1,'y','LineWidth',2)
hold on
plot(n,y2,'r','LineWidth',2)
plot(n,y3,'g','LineWidth',2)
plot(n,y4,'b','LineWidth',2)
plot(n,y5,'m','LineWidth',2)
plot(n,y6,'c','LineWidth',2)
legend('O(1)','O(log_2 n)','O(n)','O(n log_2 n)','O(n^2)','O(2^n)',2)
hold off
Data Structures 24
