School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Analysis
By:
Dr. Monika Bansal
Associate Professor, SCSE
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Run-time Analysis
• Depends on
– input size
– input quality (partially ordered)
• Kinds of analysis
– Worst case (standard)
– Average case (sometimes)
– Best case (never)
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
What do we mean by Analysis?
• Analysis is performed with respect to a
computational model
• We will usually use a generic uniprocessor random-
access machine (RAM)
– All memory is equally expensive to access
– No concurrent operations
– All reasonable instructions take unit time
• Except, of course, function calls
– Constant word size
• Unless we are explicitly manipulating bits
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Example: Searching
• Assume we have a sorted array of integers, X[1..N] and
we are searching for “key”
Cost Times
found = 0; C0 1
i = 0; C1 1
while (!found && i < N) { C2 0 <= L < N
if (key == X[i]) C3 1 <= L <= N
found = 1; C4 ?
i++; C5 1 <= L <= N
}
T(n) = C0 + C1 + L*(C2 + C3 + C4), where 1 <= L <= N is the number of times
that the loop is iterated.
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Example: Searching
• What’s the best case? Loop iterates just once =>
– T(n) = C0 + C1 + C2 + C3 + C4
• What’s the average (expected) case? Loop iterates N/2 times =>
– T(n) = C0 + C1 + N/2 * (C2 + C3 + C4)
– Notice that this can be written as T(n) = a + b*n where a, b are
constants
• What’s the worst case? Loop iterates N times =>
– T(n) = C0 + C1 + N * (C2 + C3 + C4)
– Notice that this can be written as T(n) = a + b*n where a, b are
constants
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Worst Case Analysis
• We will only look at WORST CASE running time of an
algorithm. Why?
– Worst case is an upper bound on the running time. It gives us a
guarantee that the algorithm will never take any longer
– For some algorithms, the worst case happens fairly often. As in
this search example, the searched item is typically not in the
array, so the loop will iterate N times
– The “average case” is often roughly as bad as the “worst case”.
In our search algorithm, both the average case and the worst
case are linear functions of the input size “n”
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Insertion Sort
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j = j - 1
}
A[j+1] = key
} How many times will
this loop execute?
}
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Insertion Sort
Statement Cost times
InsertionSort(A, n) {
for i = 2 to n { c1 n
key = A[i] c2 n-1
j = i - 1; c4 n-1
while (j > 0) and (A[j] > key) { c5
n
t
j =2 j
A[j+1] = A[j] c6
(t − 1)
n
j =2 j
j = j - 1 c7
(t − 1)
n
j =2 j
}
A[j+1] = key c8 n-1
}
}
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Analyzing Insertion Sort
T (n ) = c1n + c2 (n − 1) + c4 (n − 1) + c5 t j + c6 (t j − 1) + c7 (t j − 1) + c8 (n − 1)
n n n
j =2 j =2 j =2
• What can T(n) be?
– Best case -- inner loop body never executed
• ti = 1 ➔ T(n) is a linear function
– Worst case -- inner loop body executed for all previous
elements
• ti = i ➔ T(n) is a quadratic function
– Average case
• ???
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
So, Is Insertion Sort Good?
• Criteria for selecting algorithms
– Correctness
– Amount of work done
– Amount of space used
– Simplicity, clarity, maintainability
– Optimality
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Asymptotic Notation
• We will study the asymptotic efficiency of algorithms
– To do so, we look at input sizes large enough to make only the
order of growth of the running time relevant
– That is, we are concerned with how the running time of an
algorithm increases with the size of the input in the limit as the
size of the input increases without bound.
– Usually an algorithm that is asymptotically more efficient will
be the best choice for all but very small inputs.
• Real-time systems, games, interactive applications need to limit the input
size to sustain their performance.
• 3 asymptotic notations
– Big O, Q, W Notations
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Big-Oh Notation: Asymptotic Upper Bound
• T(n) = f(n) = O(g(n)) Want g(n) to be
simple.
– if f(n) <= c*g(n) for all n > n0,
c*g(n)
where c & n0 are constants > 0
f(n)
n
n0
– Example: T(n) = 2n + 5 is O(n). Why?
– 2n+5 <= 3n, for all n >= 5
– T(n) = 5*n2 + 3*n + 15 is O(n2). Why?
– 5*n2 + 3*n + 15 <= 6*n2, for all n >= 6
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
W Notation: Asymptotic Lower Bound
• T(n) = f(n) = W(g(n))
– if f(n) >= c*g(n) for all n > n0, where c and n0 are constants > 0
f(n)
c*g(n)
n
n0
– Example: T(n) = 2n + 5 is W(n). Why?
– 2n+5 >= 2n, for all n > 0
– T(n) = 5*n2 - 3*n is W(n2). Why?
– 5*n2 - 3*n >= 4*n2, for all n >= 4
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Q Notation: Asymptotic Tight Bound
• T(n) = f(n) = Q(g(n))
– if c1*g(n) <= f(n) <= c2*g(n) for all n > n0, where c1, c2 and n0 are
constants > 0
c2*g(n)
f(n)
c1*g(n)
n
n0
– Example: T(n) = 2n + 5 is Q(n). Why?
2n <= 2n+5 <= 3n, for all n >= 5
– T(n) = 5*n2 - 3*n is Q(n2). Why?
– 4*n2 <= 5*n2 - 3*n <= 5*n2, for all n >= 4
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Big-Oh, Theta, Omega
Tips to guide your intuition:
• Think of O(g(N)) as “greater than or equal to” f(N)
– Upper bound: “grows slower than or same rate as” f(N)
• Think of Ω(g(N)) as “less than or equal to” f(N)
– Lower bound: “grows faster than or same rate as” f(N)
• Think of Θ(g(N)) as “equal to” f(N)
– “Tight” bound: same growth rate
(True for large N and ignoring constant factors)
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Common Functions
Name Big-Oh Comment
Constant O(1) Can’t beat it!
Log log O(loglogN) Extrapolation search
Logarithmic O(logN) Typical time for good searching
algorithms
Linear O(N) This is about the fastest that an
algorithm can run given that we need
O(n) just to read the input
N logN O(NlogN) Most sorting algorithms
Quadratic O(N2) Acceptable when the data size is
small (N<10000)
Cubic O(N3) Acceptable when the data size is
small (N<1000)
Exponential O(2N) Only good for really small input sizes
(n<=20)
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Asymptotic Complexity
250
f(n) = n
f(n) = log(n)
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Asymptotic Complexity
500
f(n) = n
f(n) = log(n)
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Asymptotic Complexity
1000
f(n) = n
f(n) = log(n)
f(n) = n log(n)
f(n) = n^2
f(n) = n^3
f(n) = 2^n
0
1 3 5 7 9 11 13 15 17 19
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Asymptotic Complexity
5000
4000
f(n) = n
f(n) = log(n)
3000
f(n) = n log(n)
f(n) = n^2
2000 f(n) = n^3
f(n) = 2^n
1000
0
1 3 5 7 9 11 13 15 17 19
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Asymptotic Complexity
10000000
Guess
1000000
the
curves!
100000
10000
1000
100
10
1
1 4 16 64 256 1024 4096 16384 65536
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Math Review N
N ( N + 1)
• S(N) = 1 + 2 + 3 + 4 + … N =
i =1
i=
2
• Sum of Squares:
N
N * ( N + 1) * (2n + 1) N 3
i =1
i =
2
6
3
• Geometric Series:
N
1 − A N +1 A<1
i =0
A i
=
1− A
= Q(1)
N +1
N
A −1 A>1
i =0
A =
i
A −1
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Math Review
• Linear Geometric Series:
( n +1)
n
( n − 1) x − nx n
+x
i =0
ix i
= x + 2 x 2
+ 3 x 3
+ ... + nx n
=
( x − 1) 2
• Harmonic Series:
n
1 1 1 1
H n = = 1 + + + ... + = (ln n) +O(1)
i =1 i 2 3 n
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Math Review
• Logarithms:
log A B = B * log A
log( A * B) = log A + log B
A
log( ) = log A − log B
B
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Math Review
• Summations with general bounds:
b b a −1
f (i) = f (i) − f (i)
i =a i =0 i =0
• Linearity of Summations:
n n n
(4i
i =1
2
− 6i ) = 4 i − 6 i
i =1
2
i =1
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Review: Induction
• Suppose
– S(k) is true for fixed constant k
• Often k = 0
– S(n) S(n+1) for all n >= k
• Then S(n) is true for all n >= k
Program Name: BCA
David Luebke Faculty Name:
26 Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Proof By Induction
• Claim:S(n) is true for all n >= k
• Basis:
– Show formula is true when n = k
• Inductive hypothesis:
– Assume formula is true for an arbitrary n
• Step:
– Show that formula is then true for n+1
Program Name: BCA
David Luebke Faculty Name:
27 Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Induction Example: Gaussian Closed Form
• Prove 1 + 2 + 3 + … + n = n(n+1) / 2
– Basis:
• If n = 0, then 0 = 0(0+1) / 2
– Inductive hypothesis:
• Assume 1 + 2 + 3 + … + n = n(n+1) / 2
– Step (show true for n+1):
1 + 2 + … + n + n+1 = (1 + 2 + …+ n) + (n+1)
= n(n+1)/2 + n+1 = [n(n+1) + 2(n+1)]/2
= (n+1)(n+2)/2 = (n+1)(n+1 + 1) / 2
Program Name: BCA
David Luebke Faculty Name:
28 Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Induction Example:
Geometric Closed Form
• Prove a0 + a1 + … + an = (an+1 - 1)/(a - 1) for all a
1
– Basis: show that a0 = (a0+1 - 1)/(a - 1)
a0 = 1 = (a1 - 1)/(a - 1)
– Inductive hypothesis:
• Assume a0 + a1 + … + an = (an+1 - 1)/(a - 1)
– Step (show true for n+1):
a0 + a1 + … + an+1 = a0 + a1 + … + an + an+1
= (an+1 - 1)/(a - 1) + an+1 = (an+1+1 - 1)/(a - 1)
Program Name: BCA
David Luebke Faculty Name:
29 Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Induction
• We’ve been using weak induction
• Strong induction also holds
– Basis: show S(0)
– Hypothesis: assume S(k) holds for arbitrary k <= n
– Step: Show S(n+1) follows
• Another variation:
– Basis: show S(0), S(1)
– Hypothesis: assume S(n) and S(n+1) are true
– Step: show S(n+2) follows
Program Name: BCA
David Luebke Faculty Name:
30 Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “for” loops
function func(n)
1. x ← 0;
2. for i ← 1 to n do
3. for j ← 1 to n do
4. x ← x + (i - j);
5. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “for” loops
function func(n)
1. x ← 0;
2. for i ← 1 to n do
3. for j ← 1 to i do
4. x ← x + (i - j);
5. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “for” loops
function func(n)
1. x ← 0;
2. for i ← 1 to n do
3. for j ← i to n do
4. x ← x + (i - j);
5. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “for” loops
function func(n)
1. x ← 0;
2. for i ← 1 to n do
3. for j ← 1 to n do
4. x ← x + (i - j);
5. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “for” loops
function func(n)
1. x ← 0;
2. for i ← 1 to n do
3. for j ← 1 to i do
4. x ← x + (i - j);
5. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “while” loops
function func(n)
1. x ← 0;
2. i ← 0;
3. while i < n do
4. x ← x + 1;
5. i ← i + 1;
6. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “while” loops
function func(n)
1. x ← 0;
2. i ← 3;
3. while i < n do
4. x ← x + 1;
5. i ← i + 1;
6. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “while” loops
function func(n)
1. x ← 0;
2. i ← 0;
3. while i < n do
4. x ← x + 1;
5. i ← i + 3;
6. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “while” loops
function func(n)
1. x ← 0;
2. i ← 1;
3. while i < n do
4. x ← x + 1;
5. i ← i * 2;
6. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal
School of Computing Science and Engineering
Course Code : B010602T Course Name: AAD
Sample “while” loops
function func(n)
1. x ← 0;
2. i ← 1;
3. while i < n do
4. x ← x + 1;
5. i ← i * 3;
6. return(x);
Program Name: BCA Faculty Name: Dr. Monika Bansal