Formula Sheets: Asymptotic Analysis of Algorithms | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Asymptotic Analysis
Asymptotic Notations
Definitions
• Big-O (O ): f(n) = O(g(n)) if? constan ts c > 0 , n
0
> 0 suc h that f(n)= c·g(n) for all n= n
0
.
• Theta (T ): f(n) = T(g(n)) if? constan ts c
1
,c
2
> 0 , n
0
> 0 suc h that c
1
·g(n)= f(n)= c
2
·g(n) for
all n= n
0
.
• Ome ga (? ): f(n) = ?(g(n)) if? constan ts c > 0 , n
0
> 0 suc h that f(n)= c·g(n) for all n= n
0
.
• Little-o (o ): f(n) = o(g(n)) if lim
n?8
f(n)
g(n)
= 0 .
• Little-omega (? ): f(n) = ?(g(n)) if lim
n?8
f(n)
g(n)
=8 .
Prop erties
• T ransitivit y: If f(n) = O(g(n)) and g(n) = O(h(n)) , then f(n) = O(h(n)) . Similar for T , ? .
• Re flexivit y: f(n) = O(f(n)) , f(n) = T(f(n)) , f(n) = ?(f(n)) .
• Symm etry: f(n) = T(g(n)) if and only if g(n) = T(f(n)) .
• A ddition: If f
1
(n) = O(g
1
(n)) and f
2
(n) = O(g
2
(n)) , then f
1
(n)+f
2
(n) = O(max(g
1
(n),g
2
(n))) .
• Multi plication: If f
1
(n) = O(g
1
(n)) and f
2
(n) = O(g
2
(n)) , then f
1
(n)·f
2
(n) = O(g
1
(n)·g
2
(n)) .
Common F unction Classes
• Order: 1 < logn < n
?
< n < nlogn < n
2
< n
3
< 2
n
< n! < n
n
(for ? > 0 ).
Time Complexit y
Best, A v erage, W orst Case
• Best Case: Minim um running time o v er all p ossible inputs, e.g., O(n) for Bubble Sort with sorted
input.
• A v erage Case: Exp ected running time o v er all inputs, e.g., O(nlogn) for Quic k Sort with random
piv ot.
• W orst Case: Maxim um runn ing time, e.g., O(n
2
) for Quic k Sort with sorted input.
Analysis of Lo ops
• Single Lo op: for (i = 1 to n )? O(n) .
• Nested Lo op: for (i = 1 to n ) { for (j = 1 to n ) }? O(n
2
) .
• Geometric Lo op: for (i = 1 ; i= n ; i = i·2 )? O(logn) .
• Arithmetic Lo op: for (i = 1 ; i= n ; i = i+k )? O(n/k) .
• Dep enden t Lo op: for (i = 1 to n ) { for (j = 1 to i ) }? O(n(n+1)/2) = O(n
2
) .
If/While Statemen ts
• If Statemen t: O(max( then, else)) .
• While Lo op: O( iterations· b o dy complexit y) .
Recurrence Relations
Common F orms and Solutions
• Linear: T(n) = T(n-1)+c? O(n) .
• Divide-and-Conquer: T(n) = aT(n/b)+f(n) .
• Binary Searc h: T(n) = T(n/2)+O(1)? O(logn) .
1
Page 2


Asymptotic Analysis
Asymptotic Notations
Definitions
• Big-O (O ): f(n) = O(g(n)) if? constan ts c > 0 , n
0
> 0 suc h that f(n)= c·g(n) for all n= n
0
.
• Theta (T ): f(n) = T(g(n)) if? constan ts c
1
,c
2
> 0 , n
0
> 0 suc h that c
1
·g(n)= f(n)= c
2
·g(n) for
all n= n
0
.
• Ome ga (? ): f(n) = ?(g(n)) if? constan ts c > 0 , n
0
> 0 suc h that f(n)= c·g(n) for all n= n
0
.
• Little-o (o ): f(n) = o(g(n)) if lim
n?8
f(n)
g(n)
= 0 .
• Little-omega (? ): f(n) = ?(g(n)) if lim
n?8
f(n)
g(n)
=8 .
Prop erties
• T ransitivit y: If f(n) = O(g(n)) and g(n) = O(h(n)) , then f(n) = O(h(n)) . Similar for T , ? .
• Re flexivit y: f(n) = O(f(n)) , f(n) = T(f(n)) , f(n) = ?(f(n)) .
• Symm etry: f(n) = T(g(n)) if and only if g(n) = T(f(n)) .
• A ddition: If f
1
(n) = O(g
1
(n)) and f
2
(n) = O(g
2
(n)) , then f
1
(n)+f
2
(n) = O(max(g
1
(n),g
2
(n))) .
• Multi plication: If f
1
(n) = O(g
1
(n)) and f
2
(n) = O(g
2
(n)) , then f
1
(n)·f
2
(n) = O(g
1
(n)·g
2
(n)) .
Common F unction Classes
• Order: 1 < logn < n
?
< n < nlogn < n
2
< n
3
< 2
n
< n! < n
n
(for ? > 0 ).
Time Complexit y
Best, A v erage, W orst Case
• Best Case: Minim um running time o v er all p ossible inputs, e.g., O(n) for Bubble Sort with sorted
input.
• A v erage Case: Exp ected running time o v er all inputs, e.g., O(nlogn) for Quic k Sort with random
piv ot.
• W orst Case: Maxim um runn ing time, e.g., O(n
2
) for Quic k Sort with sorted input.
Analysis of Lo ops
• Single Lo op: for (i = 1 to n )? O(n) .
• Nested Lo op: for (i = 1 to n ) { for (j = 1 to n ) }? O(n
2
) .
• Geometric Lo op: for (i = 1 ; i= n ; i = i·2 )? O(logn) .
• Arithmetic Lo op: for (i = 1 ; i= n ; i = i+k )? O(n/k) .
• Dep enden t Lo op: for (i = 1 to n ) { for (j = 1 to i ) }? O(n(n+1)/2) = O(n
2
) .
If/While Statemen ts
• If Statemen t: O(max( then, else)) .
• While Lo op: O( iterations· b o dy complexit y) .
Recurrence Relations
Common F orms and Solutions
• Linear: T(n) = T(n-1)+c? O(n) .
• Divide-and-Conquer: T(n) = aT(n/b)+f(n) .
• Binary Searc h: T(n) = T(n/2)+O(1)? O(logn) .
1
• Merge Sort: T(n) = 2T(n/2)+O(n)? O(nlogn) .
Master Theorem
• F or T(n) = aT(n/b)+f(n) , where a= 1 , b > 1 :
– Case 1: If f(n) = O(n
log
b
a-?
) for ? > 0 , then T(n) = T(n
log
b
a
) .
– Case 2: If f(n) = T(n
log
b
a
log
k
n) , then T(n) = T(n
log
b
a
log
k+1
n) .
– Case 3: If f(n) = ?(n
log
b
a+?
) and af(n/b)= cf(n) for c < 1 , then T(n) = T(f(n)) .
Space Complexit y
Basics
• T otal Space: S(n) = fixed + v ariable+ auxiliary.
• Fixed: Constan ts, simple v ariables, e.g., O(1) .
• V ariable: Input size -dep enden t, e.g., arra ys of size n? O(n) .
• A uxiliary: Extra space use d b y algorithm, e.g., recursion stac k in Quic k Sort? O(logn) a v erage.
Examples
• Iterativ e Algorithms (e.g., B ubble Sort): O(1) auxiliary .
• Recursiv e Algorithms ( e.g., Merge Sort): O(n) auxiliary .
• Depth-First Searc h: O(V) for recursion stac k.
• Matrix Op erations (e .g., n×n matrix): O(n
2
) .
2