Complexity Analysis (Part II)
• Asymptotic Complexity
• Big-O (asymptotic) Notation
• Big-O Computation Rules
• Proving Big-O Complexity
• How to determine complexity of code structures
COSC 301: Data Structures .14
Asymptotic Complexity
• Finding the exact complexity, f(n) = number of basic
operations, of an algorithm is difficult.
• We approximate f(n) by a function g(n) in a way that
does not substantially change the magnitude of f(n). --
the function g(n) is sufficiently close to f(n) for large
values of the input size n.
• This "approximate" measure of efficiency is called
asymptotic complexity. G(n) is the asymptotic complexity… approx.
• Thus the asymptotic complexity measure does not
give the exact number of operations of an algorithm, but
it shows how that number grows with the size of the
input.
• This gives us a measure that will work for different
operating systems, compilers and CPUs.
.24
COSC 301: Data Structures
Big-O (asymptotic) Notation
• The most commonly used notation for specifying asymptotic
complexity is the big-O notation.
• The Big-O notation, O(g(n)), is used to give an upper bound
(worst-case) on a positive runtime function f(n) where n is the
input size.
Definition of Big-O:
• Consider a function f(n) that is non-negative n 0. We say that
“f(n) is Big-O of g(n)” i.e., f(n) = O(g(n)), if n0 0 & a constant c > 0
such that f(n) cg(n), n n0
COSC 301: Data Structures .34
Big-O (asymptotic) Notation
Implication of the definition:
• For all sufficiently large n, c *g(n) is an upper bound of
f(n)
Note: By the definition of Big-O:
f(n) = 3n + 4 is O(n)
it is also O(n2), for eg. F(n) = 3n2 + 9
it is also O(n3), for eg. F(n) = 3n3 + 3
...
it is also O(nn) for eg. F(n) = 3nn + 9
• However when Big-O notation is used, the function g in
the relationship f(n) is O(g(n)) is CHOOSEN TO BE AS
SMALL AS POSSIBLE.
– We call such a function g a tight asymptotic bound of f(n)
.44
COSC 301: Data Structures
Big-O (asymptotic) Notation
Some Big-O complexity classes in order of magnitude from smallest to highest:
Mind types of complexity class here
O(1) Constant
O(log(n)) Logarithmic
O(n) Linear
O(n log(n)) n log n
O(nx) {e.g., O(n2), O(n3), etc} Polynomial
O(an) {e.g., O(1.6n), O(2n), etc} Exponential
O(n!) Factorial
O(nn)
.54
COSC 301: Data Structures
Examples of Algorithms and their big-O complexity
Big-O Notation Examples of Algorithms
O(1) Push, Pop, Enqueue (if there is a tail reference),
Dequeue, Accessing an array element
O(log(n)) Binary search
O(n) Linear search
O(n log(n)) Heap sort, Quick sort (average), Merge sort
O(n2) Selection sort, Insertion sort, Bubble sort
O(n3) Matrix multiplication
O(2n) Towers of Hanoi
COSC 301: Data Structures .64
Warnings about O-Notation
• Big-O notation cannot compare
algorithms in the same complexity class.
• Maybe bcus they are of approximated values?
• Big-O notation only gives sensible
comparisons of algorithms in different
complexity classes when n is large .
• Consider two algorithms for same task:
Linear: f(n) = 1000 n
Quadratic: f'(n) = n2/1000
The quadratic one is faster for n < 1,000,000.
COSC 301: Data Structures .74
Rules for using big-O
• For large values of input n , the constants and terms with lower
degree of n are ignored. E.g answer = 3n3 + 2n2 + 5…….then we say O(n3)
1. Multiplicative Constants Rule: Ignoring constant factors.
O(c f(n)) = O(f(n)), where c is a constant;
Example:
O(20 n3) = O(n3)
2. Addition Rule: Ignoring smaller terms.
If O(f(n)) < O(h(n)) then O(f(n) + h(n)) = O(h(n)).
Example:
O(n2 log n + n3) = O(n3)
O(2000 n3 + 2n ! + n800 + 10n + 27n log n + 5) = O(n !)
after ignoring constants, [n! is the biggest]…you can check
table and see!
3. Multiplication Rule: O(f(n) * h(n)) = O(f(n)) * O(h(n))
Example:
O((n3 + 2n 2 + 3n log n + 7)(8n 2 + 5n + 2)) = O(n 5) add
COSCpowers
301: Data Structures .84
Proving Big-O Complexity
To prove that f(n) is O(g(n)) we find any pair of values n0 and c that
satisfy:
f(n) ≤ c * g(n) for n n0
Note: The pair (n0, c) is not unique. If such a pair exists then there is an
infinite number of such pairs.
Example: Prove that f(n) = 3n2 + 5 is O(n2)
We try to find some values of n and c by solving the following
inequality:
3n2 + 5 cn2 OR 3 + 5/n2 c since proving O(n) that’s y we use O(n )
2
(By putting different values for n, we get corresponding values for c)
n0 1 2 3 4
c 8 4.25 3.55 3.3125 3
.94
COSC 301: Data Structures
Proving Big-O Complexity
Example:
Prove that f(n) = 3n2 + 4n log n + 10 is O(n2) by finding appropriate
values for c and n0
We try to find some values of n and c by solving the following inequality
3n2 + 4n log n + 10 cn2 since we proving O(n2 ) that’s y
we used n2
OR 3 + 4 log n / n+ 10/n2 c
( We used Log of base 2, but another base can be used as well)
n0 1 2 3 4
c 13 7.5 6.22 5.62 3
COSC 301: Data Structures .104
How to determine complexity of code structures
Loops: for, while, and do-while:
Complexity is determined by the number of iterations in
the loop times the complexity of the body of the loop.
Examples:
for (int i = 0; i < n; i++)
sum = sum - i; O(n)
for (int i = 0; i < n * n; i++) O(n2)
sum = sum + i;
i=1;
while (i < n) {
sum = sum + i; O(log n)
i = i*2
}
.114
COSC 301: Data Structures
How to determine complexity of code structures
Nested Loops: Complexity of inner loop * complexity of outer loop.
Examples:
sum = 0
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) O(n2)
sum += i * j ;
i = 1;
while(i <= n) {
j = 1;
while(j <= n){
statements of constant complexity O(n log n)
j = j*2;
}
i = i+1;
}
.124
COSC 301: Data Structures
How to determine complexity of code structures
Sequence of statements: Use Addition rule
O(s1; s2; s3; … sk) = O(s1) + O(s2) + O(s3) + … + O(sk)
= O(max(s1, s2, s3, . . . , sk))
Example:
for (int j = 0; j < n * n; j++)
sum = sum + j;
for (int k = 0; k < n; k++)
sum = sum - l;
[Link]("sum is now ” + sum);
Complexity is O(n2) + O(n) +O(1) = O(n2)
COSC 301: Data Structures .134
How to determine complexity of code structures
Switch: Take the complexity of the most expensive case
char key;
int[] X = new int[n];
int[][] Y = new int[n][n];
........
switch(key) {
case 'a':
for(int i = 0; i < [Link]; i++) o(n)
sum += X[i];
break;
case 'b':
for(int i = 0; i < [Link]; j++)
for(int j = 0; j < Y[0].length; j++)
o(n2)
sum += Y[i][j];
break;
} //Overall
End ofComplexity:
switch block
O(n2)
.144
COSC 301: Data Structures
How to determine complexity of code structures
If Statement: Take the complexity of the most expensive case :
char key;
int[][] A = new int[n][n];
int[][] B = new int[n][n];
int[][] C = new int[n][n];
........
if(key == '+') {
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
C[i][j] = A[i][j] + B[i][j]; Tis well,
Something
} // End of if block
O(n2) missing at
else part…
else if(key == 'x') Overall
C = matrixMult(A, B); complexity
O(n3) O(n3)
else
[Link]("Error! Enter '+' or 'x'!");
O(1)
COSC 301: Data Structures .154
How to determine complexity of code structures
• Sometimes if-else statements must carefully be checked:
O(if-else) = O(Condition)+ Max[O(if), O(else)]
int[] integers = new int[n];
........
if(hasPrimes(integers) == true)
integers[0] = 20; O(1)
else
integers[0] = -20; O(1)
public boolean hasPrimes(int[] arr) {
for(int i = 0; i < [Link]; i++)
..........
.......... O(n)
} // End of hasPrimes()
O(if-else) = O(Condition) = O(n) .164
COSC 301: Data Structures
How to determine complexity of code structures
• Note: Sometimes a loop may cause the if-else rule not to be
applicable. Consider the following loop:
while (n > 0) {
if (n % 2 = = 0) {
[Link](n);
n = n / 2;
} else{
[Link](n);
[Link](n);
n = n – 1;
}
}
The else-branch has more basic operations; therefore one may
conclude that the loop is O(n). However the if-branch dominates.
For example if n is 60, then the sequence of n is: 60, 30, 15, 14, 7,
6, 3, 2, 1, and 0. Hence the loop is logarithmic and its complexity is
O(log n)
COSC 301: Data Structures .174