Data Structures
Program Complexities
1
Algorithms
What is an algorithm?
A sequence of elementary computational steps that transform
the input into the output
What for?
A tool for solving well-specified computational problems, e.g.,
Sorting, Matrix Multiplication
What do we need to do with an algorithm?
Correctness Proof:
for every input instance, it halts with the correct output
Performance Analysis (1 second or 10 years?):
How does the algorithm behave as the problem size gets large
both in running time and storage requirement
2
A Sorting Problem
Input : <a0, a1, … , an-1>
Output: A permutation (re-ordering) <a’0, a’1, … , a’n-1> of
the input sequence such that a’0 a’1 … a’n-1
Example:
<22, 51, 34, 44, 67, 11> => <11, 22, 34, 44, 51, 67>
3
Insertion Sort
Note that when we are
dealing with kth number, the
5, 3, 1, 2, 6, 4 first k-1 numbers are
already sorted.
3, 5, 1, 2, 6, 4
The kth number is inserted
1, 3, 5, 2, 6, 4 in the correct position.
1, 2, 3, 5, 6, 4
1, 2, 3, 5, 6, 4
1, 2, 3, 4, 5, 6
4
Insertion Sort
5, 3, 1, 2, 6, 4 To sort A[0,1,…,n-1] in place
3, 5, 1, 2, 6, 4 Steps:
1, 3, 5, 2, 6, 4 Pick element A[j]
Move A[j-1,…,0] to the right until
1, 2, 3, 5, 6, 4
proper position for A[j] is found
1, 2, 3, 5, 6, 4
1, 2, 3, 4, 5, 6 Example 1 3 5 2 6 4
0 … j j+1 . . 1 3 5 2 6 4
1 3 5 5 6 4
Currently Currently 1 3 3 5 6 4
sorted unsorted 1 2 3 5 6 4
part part
5
Insertion Sort
A[0] A[1] A[2] A[3] A[4] A[5]
Insertion-Sort (A)
1. for j=1 to n-1 j=1 5 3 1 2 6 4
2. key=A[j]
3. i=j-1
j=2 3 5 1 2 6 4
4. while i>=0 and A[i]>key j=3 1 3 5 2 6 4
5. A[i+1]=A[i]
6. i=i-1 j=4 1 2 3 5 6 4
7. A[i+1]=key j=5 1 2 3 5 6 4
1 2 3 4 5 6
j=3 1 3 5 2 6 4
1 3 5 5 6 4
1 3 3 5 6 4
1 2 3 5 6 4 6
Correctness of Algorithm
Why can the algorithm correctly sort?
We only consider algorithms with loops
Find a property as loop invariant
How to show something is loop invariant?
Initialization:
It is true prior to the first iteration of the loop
Maintenance:
If it is true before an iteration, it remains true before the
next iteration
Termination:
When the loop terminates, the invariant gives a useful
property that helps to show the algorithm is correct
7
Running time of Insertion Sort
Insertion-Sort(A) Cost times
1 for j = 1 to n-1 c1 n
2 key = A[j] n-1
3 i = j-1 c2 n-1
4 while i >= 0 and A[i] > key j=1..n-1 (tj+1)
5 A[i+1] = A[i] c3 j=1..n-1 tj
6 i=i-1 j=1..n-1 tj
c4
7 A[i+1] = key n-1
c1, c2, .. =c5running time for
executing line 1, line 2, etc.
tj = no. ofc6 times that line 5,6
are executed, for each j.
The running time T(n) c7
= c1*n+c2*(n-1)+c3*(n-1)+c4*(j=1..n-1 (tj+1))+c5*(j=1..n-1 tj)+c6*(j=1..n-1 tj)+c7*(n-1)
8
Analyzing Insertion Sort
T(n) = c1*n+c2*(n-1)+c3*(n-1)+c4*(j=1..n-1 (tj+1))+
c5*(j=1..n-1 tj)+c6*(j=1..n-1 tj)+c7*(n-1)
Worse case:
Reverse sorted: for example 6,5,4,3,2,1
inner loop body executed for all previous elements.
tj=j.
T(n) = c1*n+c2*(n-1)+c3*(n-1)+c4*(j=1..n-1 (j+1))+
c5*(j=1..n-1 j)+c6*(j=1..n-1 j)+c7*(n-1)
T(n) = An2+Bn+C Note: j=1..n-1 j = n(n-1)/2
j=1..n-1 (j+1) = (n+2)(n-1)/2
9
Analyzing Insertion Sort
T(n)=c1*n+c2*(n-1)+c3*(n-1)+c4*(j=1..n-1 (tj+1))+c5*(j=1..n-1 tj)+c6*(j=1..n-1 tj)+c7*(n-1)
Worst case Reverse sorted inner loop body executed for all
previous elements. So, tj=j.
T(n) is quadratic: T(n)=An2+Bn+C
Average case Half elements in A[0..j-1] are less than A[j]. So, tj = j/2
T(n) is also quadratic: T(n)=An2+Bn+C
Best case Already sorted inner loop body never executed. So,
tj=0.
T(n) is linear: T(n)=An+B 10
Kinds of Analysis
(Usually) Worst case Analysis:
T(n) = max time on any input of size n
Knowing it gives us a guarantee about the upper bound.
In some cases, worst case occurs fairly often
(Sometimes) Average case Analysis:
T(n) = average time over all inputs of size n
Average case is often as bad as worst case.
(Rarely) Best case Analysis:
Cheat with slow algorithm that works fast on some input.
Good only for showing bad lower bound.
11
Kinds of Analysis
Worst case
Average case
Best case
0 1 2 3 4 n
Worst Case: maximum value
Average Case: average value
Best Case: minimum value 12
Order of Growth
Examples:
Running time of algorithm in microseconds
(in term of data size n)
f(n) n=20 n=40 n=60
Algorithm A Log2n 4.32 * 10-6sec 5.32 * 10-6sec 5.91 * 10-6sec
Algorithm B Sqrt(n) 4.47 * 10-6sec 6.32 * 10-6sec 7.75 * 10-6sec
Algorithm C n 20 * 10-6sec 40 * 10-6sec 60 * 10-6sec
Algorithm D n log2n 86 * 10-6sec 213 * 10-6sec 354 * 10-6sec
Algorithm E n2 400 * 10-6sec 1600 * 10-6sec 3600 * 10-6sec
Algorithm F n4 0.16 sec 2.56 sec ______ sec
Algorithm G 2n 1.05 sec 12.73 days ______ years
Algorithm H n! 77147 years 2.56 * 1034 years 2.64 * 1068 years
13
Order of Growth
Assume: an algorithm can solve a problem of size n in f(n) microseconds
(10-6 seconds).
f(n)
90000
log2n
80000
microseconds
70000 Sqrt n
60000 n
50000 nlog2n
40000 n2
30000
n4
20000
2n
10000
0 n n!
Note: for example,
For all f(n) in (n4), the shapes of their curves are nearly the same 14as
f(n)=n4.
Asymptotic Notation
How can we indicate running times of
algorithms?
Need a notation to express the growth rate
of a function
A way to compare “size” of functions:
-notation (“Big-oh”) (upper bound)
-notation (“Big-omega”) (lower bound)
-notation ( “theta”) (sandwich)
2015-16B Complexity Analysis 15
-notation (1/2)
-notation provides an asymptotic upper
bound of a function.
For a given function g(n), we denote
(g(n)) (pronounced “big-oh” of g of n) by
the set of functions: f(n) = (g(n))
(g(n)) = {f(n): there exist positive
constants c and n0 such that
0 f(n) cg(n) for all n n0}
2015-16B Complexity Analysis 16
-notation (2/2)
We write f(n) = (g(n)) to
Indicate that f(n) is a member of the set (g(n))
Give that g(n) is an upper bound for f(n) to
within a constant factor
Example: 2n2 = (n3), with c = 1 and n0 =
2
When n = 1: 2(1)2 = 2 (1)3 = 1
When n = 2: 2(2)2 = 8 (2)3 = 8
When n = 3: 2(3)2 = 18 (3)3 = 27
2015-16B Complexity Analysis 17
-notation (1/2)
-notation provides an asymptotic lower
bound of a function.
For a given function g(n), we denote
(g(n)) (pronounced “big-omega” of g of n)
by the set of functions: f(n) = (g(n))
(g(n)) = {f(n): there exist positive
constants c and n0 such that
0 cg(n) f(n) for all n n0}
2015-16B Complexity Analysis 18
-notation (2/2)
We write f(n) = (g(n)) to
Indicate that f(n) is a member of the set (g(n))
Give that g(n) is a lower bound for f(n) to within
a constant factor
Example: n2 + n = (n2), with c = 1 and
n0=1
When n = 1: (1)2 + 1 = 2 (1)2 = 1
When n = 2: (2)2 + 2 = 6 (2)2 = 4
When n = 3: (3)2 + 3 = 12 (3)2 = 9
2015-16B Complexity Analysis 19
-notation (1/2)
-notation provides an asymptotically
tight bound of a function.
For a given function g(n), we denote
(g(n)) (pronounced “theta” of g of n) by
the set of functions: f(n) = (g(n))
(g(n)) = {f(n): there exist
positive constants c1, c2 and n0
such that 0 c1g(n) f(n)
c2g(n) for all n n0}
2015-16B Complexity Analysis 20
-notation (2/2)
Theorem
f(n) = (g(n)) if and only if f(n) = (g(n)) and f(n) =
(g(n))
Example: n2/2 - 2n = (n2), with c1 = 1/4,
c2=1/2, and n0 = 8
When n = 7: 1/4[(7)2] = 12.25 (7)2/2 - 2(7) = 10.5
1/2[(7)2] = 24.5
When n = 8: 1/4[(8)2] = 16 (8)2/2 - 2(8) = 16
1/2[(8)2] = 32
When n = 9: 1/4[(9)2] = 20.25 (9)2/2 - 2(9) = 22.5
1/2[(9)2] = 40.5
2015-16B Complexity Analysis 21
O versus o
What about “<”?
o versus O : o means better e.g. n=o(n2)
Why 100n=O(n)?
When n is very big like 10000000000000000
100n: 1000000000000000000
n: 10000000000000000
nearly the same
Why n=o(n2)?
When n is 10000000000000000
n2 is 100000000000000000000000000000000
Differ a lot! 22
Asymptotic Notation
Relationship between typical functions
log n = o (n)
n = o (n log n)
nc = o (2n) where nc may be n2, n4, etc.
If f(n)=n+log n, we call log n lower order terms
(You are not required to analyze, but remember these
relations)
log n < sqrt(n) < n < nlog n < n2 < n4 < 2n < n!
23
Asymptotic Notation
When calculating asymptotic running time
Drop low-order terms
Ignore leading constants
Example 1: T(n) = An2+Bn+C
An2
T(n) = O(n2)
Example 2: T(n) = Anlogn+Bn2+Cn+D
Bn2
T(n) = O(n2)
24
Asymptotic Performance
Insertion-Sort(A)
Very often the 1 for j = 1 to n-1
O(n2)
algorithm 2 key = A[j]
complexity can 3 i = j-1
be observed 4 while i >= 0 and A[i] > key
directly from 5 A[i+1] = A[i]
simple 6 i=i-1
algorithms 7 A[i+1] = key
There are 4 very useful rules for such Big-Oh analysis ...
25
Asymptotic Performance
General rules for Big-Oh Analysis:
Rule 1. FOR LOOPS Rule 2. NESTED FOR LOOPS
The running time of a for loop is at The total running time of a
most the running time of the statement inside a group of nested
statements inside the for loop loops is the running time of the
(including tests) times no. of iterations statement multiplied by the product
of the sizes of all the loops.
for (i=0;i<N;i++)
a++; O(N) for (i=0;i<N;i++)
for (j=0;j<N;j++)
k++; O(N2)
Rule 3. CONSECUTIVE STATEMENTS
Count the maximum one. Rule 4. IF / ELSE
for (i=0;i<N;i++) For the fragment:
O(N2)
a++; If (condition) take the test +
S1 the maximum
for (i=0;i<N;i++)
else for S1 and S2.
for (j=0;j<N;j++) S2,
26
k++;
Asymptotic Performance
Example of Big-Oh Analysis:
void function1(int n) void function2(int n)
{ int i, j; { int i;
int x=0; int x=0;
for (i=0;i<n;i++) for (i=0;i<n/2;i++)
x++; x++;
}
for (i=0;i<n;i++)
for (j=0;j<n;j++) This function is O(__)
x++;
}
This function is O(__)
27
Asymptotic Performance
Example of Big-Oh Analysis:
void function3(int n) void function4(int n)
{ int i; { int i;
int x=0; int x=0;
if (n>10) for (i=0;i<10;i++)
for (i=0;i<n/2;i++) for (j=0;j<n/2;j++)
x++; x--;
else }
{ for (i=0;i<n;i++)
for (j=0;j<n/2;j++) This function is O(__)
x--;
}
}
This function is O(__)
28
Asymptotic Performance
Example of Big-Oh Analysis:
void function5(int n)
{ int i;
for (i=0;i<n;i++)
Suppose
if (IsSignificantData(i)) IsSignificantData is O(n),
SpecialTreatment(i); SpecialTreatment is O(n log n)
This function is O(____)
29
Comparison of Good and Bad
Coin Flipping
There are N rows of coins
Each row consists of 9 coins
They formulate a matrix of size N*9
Some coins are heads up and some are tails up
We can flip a whole row or a whole column
every time
Your program need to find a flipping method
that can make the number of “heads up” coins
maximum
30
Asymptotic Performance
Recursion
int Power(int base,int pow)
{ if (pow==0) return 1;
else return base*Power(base,pow-1);
}
Example
32=9
Power(3,2)=3*Power(3,1)
Power(3,1)=3*Power(3,0)
Power(3,0)=1
T(n): the number of multiplications needed to compute Power(3,n)
T(n)=T(n-1)+1; T(0)=0
T(n)=n
Function T(n) is O(n)
31
Asymptotic Performance
Why recursion?
Can’t we just use iteration (loop)?
The reason for recursion
Easy to program in some situations
Disadvantage
More time and space required
Example:
Tower of Hanoi Problem
32
Tower of Hanoi
Given some rods for stacking disks.
The problem:
Rules: Use fewest steps to move all disks
from the source rod to the target
(1) The disks must be stacked in
without violating the rules through
order of size. the whole process (given one
(2) Each time move 1 disk. intermediate rod for buffering)?
a source rod an intermediate rod a target rod 33
Tower of Hanoi
Suppose you can manage the n-1 disks
How do you solve the n disks case?
A recursive solution:
Step 1: Move the top n-1 disks from source rod
to intermediate rod via target rod
Step 2: Move the largest disk from source rod
to target rod
Step 3: Move the n-1 disks from intermediate
rod to target rod via source rod
34
Tower of Hanoi
void Towers (int n, int Source, int Target, int Interm)
{ if (n==1)
cout<<“From”<<Source<<“To”<<Target<<endl;
else
{ Towers(n-1, Source, Interm, Target);
Towers(1, Source, Target, Interm);
Towers(n-1, Interm, Target, Source);
}
}
How many “cout” are executed?
T(n)=2T(n-1)+1
35
Recursive Relation
T(n)=T(n-1)+A; T(1)=1
T(n)=O(n)
T(n)=T(n-1)+n; T(1)=1
T(n)=O(n2)
T(n)=2T(n/2) + n; T(1)=1
T(n)=O(n log n)
More general form: T(n)=aT(n/b)+cn
Master’s Theorem
(You are not required to know)
36
Learning Objectives
1. Understand the meaning of O and o and
able to use
2. Analyze program complexities for simple
programs
3. Able to compare which function grows
faster
4. Able to do worst case analysis
D:1; C:1,2; B:1,2,3; A:1,2,3,4
37
