02_Algorithm_Analysis

Algorithms Analysis
Learning Outcomes
 To be able to:
 Carry out simple asymptotic analysis of algorithms
 Explain the use of big O, omega, and theta notation to
describe the efficiency of an algorithm
 Use big O, omega, and theta notation to give asymptotic
upper, lower, and tight bounds on time and space complexity
of algorithms
 Determine the time and space complexity of simple
algorithms
2
Scope
 Efficiency goals
 The concept of algorithm analysis
 The concept of asymptotic complexity
 Rules for using big-O
 Comparing various growth functions
 How to determine complexity of code structures
3
Introduction
 An algorithm is a clearly speciﬁed set of simple instructions to be followed to
solve a problem.
 Once an algorithm is given for a problem and decided (somehow) to be correct,

an important step is to determine how much in the way of resources, such as
time or space, the algorithm will require.
 An algorithm that solves a problem but requires a year is hardly of any use.
Likewise, an algorithm that requires hundreds of gigabytes of main memory is
not (currently) useful on most machines.
 To evaluate an algorithm’s efficiency, real-time units such as microseconds and

nanoseconds should not be used. Rather, logical units that express a
relationship between the size n of a file or an array and the amount of time t
required to process the data should be used.
4
Algorithm Efficiency
 The efficiency of an algorithm is usually expressed in terms of its

use of CPU time
 The analysis of algorithms involves categorizing an algorithm in

terms of efficiency
 An everyday example: washing dishes
 Suppose washing a dish takes 30 seconds and drying a dish takes

an additional 30 seconds
 Therefore, n dishes require n minutes to wash and dry
5
Computational Complexity
 The same problem can frequently be solved with different algorithms which
differ in efficiency.
 Computational complexity is a measure of the degree of difficulty of an

algorithm and it is used to compare the efficiency of algorithms.
 Computational complexity indicates how much effort is needed to apply an

algorithm or how costly it is. This cost can be measured in a variety of ways.
 The efficiency of execution of an algorithm depends on the hardware,

programming language used, compiler, programming skill, etc.
 To evaluate an algorithm’s efficiency, logical time units that express a

relationship between the size of an input and the amount of time and space
required to process the input should be used.
6
Machine Independence
 The evaluation of efficiency should be as machine independent as possible.
 It is not useful to measure how fast the algorithm runs as this depends on
which particular computer, OS, programming language, compiler, and kind
of inputs are used in testing
 Instead,
 we count the number of basic operations the algorithm performs.
 we calculate how this number depends on the size of the input.
 A basic operation is an operation which takes a constant amount of time to

execute.
 Hence, the efficiency of an algorithm is the number of basic operations it

performs. This number is a function of the input size n.
7
Example of Basic Operations
 Arithmetic operations: *, /, %, +, -
 Assignment statements of simple data types
 Reading of primitive types
 Writing of a primitive types
 Simple conditional tests: if (x < 12) ...
 Method call (Note: the execution time of the method itself may depend on the value
of parameter and it may not be constant)
 A method's return statement
 Memory Access
 We consider an operation such as ++ , += , and *= as consisting of two basic

operations.
 Note: To simplify complexity analysis we will not consider memory access (fetch or
store) operations. 8
Problem Size
 For every algorithm we want to analyze, we need to define the size of the
problem
 The dishwashing problem has a size n – number of dishes to be
washed/dried
 For a search algorithm, the size of the problem is the size of the search pool
 For a sorting algorithm, the size of the program is the number of elements to
be sorted
 The majority of algorithms varies its number of steps based on the size of
instance
 The efficiency of an algorithm is always stated as a function of the problem
size
 We generally use the variable n to represent the problem size
 Typically the size of the input (n) is the main consideration
9
Problem/Input size matters!
Some example algorithms and their expected running times based on
the input size
10
Growth Functions
 We must also decide what we are trying to efficiently optimize

 time complexity – CPU time
 space complexity – memory space
 CPU time is generally the focus
 The rates of growth are expressed as functions, which are generally

in terms of the number of inputs n
 A growth function shows the relationship between the size of the

problem (n) and the value we hope to optimize (time). This function
represents the time complexity or space complexity of the algorithm.
11
Algorithm Complexity
 Worst Case Complexity:

 The function defined by the maximum number of steps taken on any
instance of size n
 Best Case Complexity:

 The function defined by the minimum number of steps taken on any
instance of size n
 Average Case Complexity:

 The function defined by the average number of steps taken on any
instance of size n
12
Algorithm Complexity (cont…)
 We are usually interested in the worst case complexity: what are the most
operations that might be performed for a given problem size.
 Best case depends on the input
 Average case is difficult to compute
 So we usually focus on worst case

analysis
 Easier to compute
 Usually close to the actual running time
 Crucial to real-time systems
(e.g. air-traffic control)
13
Algorithm Complexity (cont…)
 Example: Linear Search Complexity
 Best Case: Item found at the beginning: One comparison
 Worst Case: Item found at the end: n comparisons
 Average Case: Item may be found at index 0, or 1, or 2, . . . or n - 1

 Average number of comparisons is: (1 + 2 + . . . + n) / n = (n + 1) / 2
 Worst and Average complexities of common sorting algorithms:
Method Worst Case Average Case

Selection sort n2 n2
Inserstion sort n2 n2
Merge sort n log n n log n
Quick sort n2 n log n
14
Running Time Analysis
15
Asymptotic Complexity
 It is not typically necessary to know the exact growth function for an

algorithm
 Finding the exact complexity, f(n) = number of basic operations, of

an algorithm is difficult
 We are mainly interested in the asymptotic complexity of an

algorithm – the general nature of the algorithm as n increases
 Asymptotic complexity is based on the dominant term of the growth

function – the term that increases most quickly as n increases
16
Asymptotic Complexity (cont…)
 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.
 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.
 Asymptotic bounds are used to estimate the efficiency of algorithms by

assessing the amount of time and memory needed to accomplish the task
for which the algorithms were designed.
17
Asymptotic Notations
 Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.
 Ο Notation
 Ω Notation
 θ Notation
 O(expression) gives an upper bound on the growth rate of a function. It specifically

describes the worst-case scenario or the longest amount of time an algorithm can
possibly take to complete.
 Omega(expression) gives a lower bound on the growth rate of a function. It measures

the best case time complexity or the best amount of time an algorithm can possibly
take to complete.
 Theta(expression) consist of all the functions that lie in both O(expression) and
Omega(expression). When the upper and lower bounds are the same within a constant
factor, we indicate this by using θ(big-Theta) notation. 18
Asymptotic Notations (cont…)
Meanings of the various growth functions
19
Big-Oh Notation
 The most commonly used notation for specifying asymptotic complexity is the big-O
notation.
 The coefficients and the lower order terms become increasingly less relevant as n
increases
 So we say that the algorithm is order n2, which is written O(n2)
 This is called Big-Oh notation
 There are various Big-Oh categories
 Two algorithms in the same category are generally considered to have the same
efficiency, but that doesn't mean they have equal growth functions or behave exactly
the same for all values of n
 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.
20
Big-O Notation: Definition
 Big O:
 T(n) = O(f(n)) if there are positive constants c and N
such that T(n) ≤ c f(n) when n ≥ N
 This says that function T(n) grows at a rate no faster than f(n) ; thus f(n) is
an upper bound on T(n).
 Another way:
f(n) is O(g(n))↔ there exist numbers c, N > 0

such that for each n ≥ N
f(n) ≤ c g(n)
The meaning:
• f(n) is larger than g(n) only for finite number of n’s;
• a constant c and a value N can be found so that for every value of n ≥ N: f(n) ≤ c g(n);
• f(n) does not grow more than a constant factor faster than g(n).
21
Big-O Notation: illustration
c g(n)
f(n) T(n) = O(f(n))
N n
22
Big-Ω Notation: Definition
 Big Omega:
 T(n) = Ω(f(n)) if there are positive constants c
and N such that T(n) ≥ c f(n) when n ≥ N
 This says that function T(n) grows at a rate no slower than f(n) ;
thus f(n) is a lower bound on T(n).
 Another way:
f(n) is Ω(g(n))↔ there exist numbers c, N > 0

f(n) ≥ c g(n)
23
Big-Ω Notation: illustration
T(n) = Ω(f(n))
Big-θ Notation
 The definitions of big-Oh and Ω allow describing the upper

bound of an algorithm and the lower bound of an algorithm
 When the upper and lower bounds are the same within a
constant factor, we indicate this by using Θ (big-Theta) notation.
 An algorithm is said to be Θ(h(n)) if it is in O(h(n)) and it is in

Ω(h(n)).
25
Big-θ Notation: Definition
 Big Theta:
 T(n) = θ(f(n)) if and only if
T(n) = O(f(n)) and T(n) = Ω(f(n))
 This says that function T(n) grows at the same rate as f(n) .
 Another way:
f(n) is θ(g(n))↔ there exist numbers c1, c2, N > 0

c1 g(n) ≤ f(n) ≤ c2 g(n)
big-Ω notation big-O notation
26
Big-θ Notation: illustration
c2 g(n)
f(n)
c1 g(n)
N n
Big-Oh Categories
 Some sample growth functions and their Big-Oh

categories:
28
Rules for using big-O
 For large values of input n, the constants and terms with lower
degree of n are ignored.
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)
29
Rules for using big-O (cont…)
2. Addition Rule: Ignoring smaller terms.
 If O(f(n)) < O(h(n)), then O(f(n) + h(n)) = O(h(n)).
 i.e. If T1(n) = O(f(n)) and T2(n) = O(g(n)), then
T1(n) + T2(n) = max(O(f(n)), O(g(n)))
 Example 1:
O (n2 log n + n3) = O(n3)
O (2000 n3 + 2n! + n800 + 10n + 27n log n + 5) = O(n!)
 Example 2 (Algorithm A):
Step 1: Run algorithm A1 that takes O(n3) time
Step 2: Run algorithm A2 that takes O(n2) time
TA(n) = TA1(n) + TA2(n) = O(n3) + O(n2) = max (O(n3), O(n2)) = O(n3)
30
3. Multiplication Rule:
 O(f(n) * h(n)) = O(f(n)) * O(h(n))
 i.e. If T1(n) = O(f(n)) and T2(n) = O(g(n)),

then
T1(n) * T2(n) = O(f(n)) * O(g(n))
 Example:
O((n3 + 2n2 + 3n log n + 7) (8n2 + 5n + 2)) = O(n5)
31
4. If T(n) is a polynomial of degree k, then
T(n) = O(nk)
 Example:
T(n) = n8 + 3n5 + 4n2 + 6 = O(n8)
logk(n) = O(n) for any constant k
32
Comparing Algorithms
 Establish a relative order among different algorithms, in terms of their relative rates
of growth
 The rates of growth are expressed as functions, which are generally in terms of the
number of inputs n
 Example: A simple comparison:
 Let’s assume that you have 3 algorithms to sort a list

 f(n) = n log2 n
 g(n) = n2
 h(n) = n3
 Let’s also assume that each step takes 1 microsecond (10-6)
n n log n n^2 n^3

10 33.2 100 1000
100 664 10000 1seg
1000 9966 1seg 16min
100000 1.7s 2.8 hours 31.7 years
33
Comparing Growth Functions
 You might think that faster processors would make efficient

algorithms less important
 A faster CPU helps, but not relative to the dominant term
34
Comparing Growth Functions (cont…)
 A hierarchy of growth rates:
c < log n < log2 n < logk n < n < n log n

< n2 < n3 < 2n < 3n < n! < nn
35
 As n increases, the various growth functions diverge dramatically:
36
37
How to determine complexity of code structures
NOTE : In general,
doing something with every item in one dimension is linear,
doing something with every item in two dimensions is quadratic,
and dividing the working area in half is logarithmic.
38
Analyzing Loop Execution
 Loops: for, while, and do-while:
 First determine the order of the body of the loop, then multiply that by the
number of times the loop will execute
for (int count = 0; count < n; count++)
// some sequence of O(1) steps
 N loop executions times O(1) operations results in a O(n) efficiency
 Consider the following loop:
count = 1;
while (count < n)
{
count *= 2;
}
 The loop is executed log2n times, so the loop is O(log n)

39
Analyzing Loop Execution (cont…)
 Loops: for, while, and do-while:
 Again: complexity is determined by the number of iterations in the loop
times multiplied by 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
}
40
 We start by considering how to count operations in for-loops.
 First of all, we should know the number of iterations of the loop; say it is x.
 Then the loop condition is executed x + 1 times.
 Each of the statements in the loop body is executed x times.
 The loop-index update statement is executed x times.
 Example:
int sum (int n) Time Units to Compute:
{ ------------------------
• 1 for the assignment
int partial_sum = 0; • Loop Statement: 1 assignment, n+1 tests, and
int i; n increments
• Loop Body: n loops of 3 units for:
for (i = 1; i <= n; i++) (an assignment, an addition, and multiplications)
partial_sum = partial_sum + (i * i); • 1 for the return statement
------------------------
return partial_sum; Total: 1 + (1 + n + 1 + n) + 3n + 1
} = 5n + 4 = O(n)
41
 Loops (with <):
 In the following for-loop:

for (int i = k; i < n; i = i + m){
statement1;
statement2;
}
 The number of iterations is: (n – k ) / m
 The initialization statement, i = k, is executed one time.
 The condition, i < n, is executed (n – k ) / m + 1 times.
 The update statement, i = i + m, is executed (n – k ) / m times.
 Each of statement 1 and statement 2 is executed (n – k ) / m times.
42
 Loops (with <=):
 In the following for-loop:
for (int i = k; i <= n; i = i + m){

statement1;
statement2;
}
 The number of iterations is: (n – k) / m + 1
 The initialization statement, i = k, is executed one time.
 The condition, i <= n, is executed (n – k) / m + 1 + 1 times.
 The update statement, i = i + m, is executed (n – k) / m + 1 times.
 Each of statement 1 and statement 2 is executed (n – k) / m + 1 times.
43
 Loop example:
 Find the exact number of basic operations in the following program fragment:
double x, y;
x = 2.5 ; y = 3.0;
for(int i = 0; i < n; i++){
a[i] = x * y;
x = 2.5 * x;
y = y + a[i];
}
 There are 2 assignments outside the loop  2 operations
 The for loop actually comprises
 an assignment (i = 0)  1 operation
 a test (i < n)  n + 1 operations
 an increment (i++)  2 n operations
 the loop body that has three assignments, two multiplications, and an addition  6 n operations
Thus the total number of basic operations is 6 * n + 2 * n + (n + 1) + 3 = 9n + 4
44
 Loops With Logarithmic Iterations:
 In the following for-loop: (with <)
for (int i = k; i < n; i = i * m){

statement1;
statement2;
}
 The number of iterations is: (Logm (n / k) )
 In the following for-loop: (with <=)
for (int i = k; i <= n; i = i * m){

statement1;
statement2;
}
 The number of iterations is: (Logm (n / k) + 1)
45
Analyzing Nested Loops:
 When loops are nested, we multiply the complexity of the outer loop
by the complexity of the inner loop
for (int count = 0; count < n; count++)
for (int count2 = 0; count2 < n; count2++)
 Both the inner and outer loops have complexity of O(n)
 The overall efficiency is O(n2)
46
 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;
}
47
 Nested Loops: Complexity of inner loop * complexity of outer loop
 Example:
for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++) 3mn = O(mn)
sum = sum + i + j;
 The overall efficiency of the above example is O(mn).
 Example:
for(int i = 1; i <= n; i++)

for(int j = 1; j <= m; j++)
for(int k = 1; k <= p; k++)
4pmn = O(pmn)
sum = sum + i + j + k;
48
Analyzing Sequence of Statements
 Consecutive statements: Use Addition rule
 These just add, and the maximum is the one that counts
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;
System.out.print("sum is now ” + sum);
 Complexity is O(n2) + O(n) + O(1) = O(n2)

49
Analyzing Sequence of Statements (cont…)
Example:
for (i = 1; i <= n; i++)

O(n)
sum = sum + i;
for (i = 1; i <= n; i++) {

for (j = 1; j <= n; j++) O(n2)
sum = sum + i + j;
}
 Complexity is O(n2 + + n) = O(n2)
50
Analyzing Sequence of Statements (cont…)
 Example:
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) O(n2)
sum = sum + i + j;
sum = sum / n; O(1)

for (i = 1; i <= n; i++)
sum = sum + i;
O(n)
for (j = 1; j <= n; j++)

O(n)
sum = sum + j * j;
 n2 + + 1 + n + n = O(n2 + 2n + 1) = O(n2)
51
Analyzing If Execution
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++) Overall
C[i][j] = A[i][j] + B[i][j]; O(n2)
complexity
} // End of if block O(n3)
else if(key == 'x')
C = matrixMult(A, B);
O(n3)
else
System.out.println("Error! Enter '+' or 'x'!"); O(1)
52
Analyzing If Execution (cont…)
 if (test) s1 else s2
 The running time is never more than the running time of the test plus the larger
of the running times of s1 and s2
 Example:
if (test == 1) O(1)
for (i = 1; i <= n; i++)
sum = sum + i; O(n)
else
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) O(n2)
sum = sum + i + j;
 The running time = 1 + max(n, n2) = O(n2)

53
 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 < arr.length; i++)
..........
.......... O(n)
} // End of hasPrimes()
O(if-else) = O(Condition) = O(n)

54
 Example (complexity of a code fragment which include if statement):
for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
sum = sum + i + j + k;
The Running Time:
= O(n3) + O(n2)
if (test == 1)
for (i = 1; i <= n; i++) = O(n3)
for(j = 1; j <= n; j++)
sum = sum + i;
else
for (i = 1; i <= n; i++)
sum = sum + i + j;
55
 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) {
System.out.println(n);
n = n / 2;
}
else {
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)
56
Analyzing Switch Execution
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 < X.length; i++) o(n)
sum += X[i];
break;
case 'b':
for(int i = 0; i < Y.length; j++) o(n2)
for(int j = 0; j < Y[0].length; j++)
sum += Y[i][j];
break;
} // End of switch block
Overall Complexity: O(n2)

57
Analyzing Method Calls
 The body of a loop may contain a call to a method
 To determine the order of the loop body, the order of

the method must be taken into account
 The overhead of the method call itself is generally

ignored
58
Analyzing Method Calls (cont…)
 Loop example:
 Suppose n is a multiple of 2. Determine the number of basic operations performed by of the
method myMethod():
static int myMethod(int n){ static int helper(int n){
int sum = 0; int sum = 0;
for(int i = 1; i < n; i = i * 2) for(int i = 1; i <= n; i++)
sum = sum + i + helper(i); sum = sum + i;
return sum; return sum;
} }
 Solution: The number of iterations of the loop:
for (int i = 1; i < n; i = i * 2)
sum = sum + i + helper(i);
is log2n
Hence the number of basic operations is:
1 + 1 + (1 + log2n) + log2n[2 + 4 + 1 + 1 + (n + 1) + n[2 + 2] + 1] + 1
= 3 + log2n + log2n[10 + 5n] + 1 = 5 n log2n + 11 log2n + 4

59
Analyzing Method Calls (cont…)
 Recursion:
 Analyze from the inside (or deepest part) first and work outwards. If there are
function calls, these must be analyzed first.
 Example:
long factorial (int n) { Time Units to Compute:
if (n <= 1) ------------------------
return 1; 1 for the test
else 1 for the multiplication statement
return n * factorial (n – 1);
} What about the function call?
 The running time of factorial(n) = T(n) = 2 + T(n-1) =
4 + T(n-2) = 6 + T(n-3) = … = 2n = O(n)

60
Examples of Algorithms and their big-O complexity
Big-O Notation Examples of Algorithms
Push, Pop, Enqueue (if there is a tail reference), Dequeue,

O(1)
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
61
Summary
 Software must make efficient use of resources such as CPU time and memory.
 Algorithm analysis is a fundamental computer science topic.
 A growth function shows time or space utilization relative to the problem size.
 The order of an algorithm is found by eliminating constants and all but the dominant term in the
algorithm’s growth function.
 The order of an algorithm provides an upper bound to the algorithm’s growth function.
 If the algorithm is inefficient, a faster processor will not help in the long run.
 Analyzing algorithm complexity often requires analyzing the execution of loops.
 The time complexity of a loop is found by multiplying the complexity of the body of the loop by
how many times the loop will execute.
 The analysis of nested loops must take into account both the inner and outer loops.
 If and Switch statements: take the complexity of the most expensive case.
 If there are function calls, these must be analyzed first.
62
References
 Java Software Structures, - Designing and Using Data Structures,4th edition, Lewis and Chase
 Data Structures and Problem Solving Using Java, 4th edition, Weiss
 Data Structures & Algorithms in Java, 3rd edition, Drozdek
 Data Structures and Algorithm Analysis in Java, 3rd edition, Weiss
 Algorithms, 4th edition, Sedgewick and Wayne
 A Practical Introduction to Data Structures and Algorithm Analysis, 3rd edition, Shaffer
 Data Structures and Algorithms in Java, 6th edition, Goodrich, Tamassia and Goldwasser
 Slides at: http://faculty.kfupm.edu.sa/ICS/jauhar/ics202/
63
Any Question
???
64

02_Algorithm_Analysis

Uploaded by

Copyright:

Available Formats

02_Algorithm_Analysis

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

02_Algorithm_Analysis

Uploaded by

Copyright:

Available Formats

Algorithms Analysis

 The concept of algorithm analysis

 The concept of asymptotic complexity

 Rules for using big-O

 Comparing various growth functions

 How to determine complexity of code structures

 Once an algorithm is given for a problem and decided (somehow) to be correct,

 To evaluate an algorithm’s efficiency, real-time units such as microseconds and

 The efficiency of an algorithm is usually expressed in terms of its

 The analysis of algorithms involves categorizing an algorithm in

 An everyday example: washing dishes

 Suppose washing a dish takes 30 seconds and drying a dish takes

 Therefore, n dishes require n minutes to wash and dry

 Computational complexity is a measure of the degree of difficulty of an

 Computational complexity indicates how much effort is needed to apply an

 The efficiency of execution of an algorithm depends on the hardware,

 To evaluate an algorithm’s efficiency, logical time units that express a

 we count the number of basic operations the algorithm performs.

 we calculate how this number depends on the size of the input.

 A basic operation is an operation which takes a constant amount of time to

 Hence, the efficiency of an algorithm is the number of basic operations it

 Assignment statements of simple data types

 Reading of primitive types

 Writing of a primitive types

 Simple conditional tests: if (x < 12) ...

 A method's return statement

 We consider an operation such as ++ , += , and *= as consisting of two basic

 We must also decide what we are trying to efficiently optimize

 space complexity – memory space

 CPU time is generally the focus

 The rates of growth are expressed as functions, which are generally

 A growth function shows the relationship between the size of the

 Worst Case Complexity:

 Best Case Complexity:

 Average Case Complexity:

 Best case depends on the input

 Average case is difficult to compute

 So we usually focus on worst case

 Usually close to the actual running time

 Crucial to real-time systems

(e.g. air-traffic control)

 Example: Linear Search Complexity

 Best Case: Item found at the beginning: One comparison

 Worst Case: Item found at the end: n comparisons

 Average Case: Item may be found at index 0, or 1, or 2, . . . or n - 1

 Worst and Average complexities of common sorting algorithms:

Method Worst Case Average Case

 It is not typically necessary to know the exact growth function for an

 Finding the exact complexity, f(n) = number of basic operations, of

 We are mainly interested in the asymptotic complexity of an

 Asymptotic complexity is based on the dominant term of the growth

 This "approximate" measure of efficiency is called asymptotic complexity.

 Asymptotic bounds are used to estimate the efficiency of algorithms by

 O(expression) gives an upper bound on the growth rate of a function. It specifically

 Omega(expression) gives a lower bound on the growth rate of a function. It measures

Meanings of the various growth functions

 So we say that the algorithm is order n2, which is written O(n2)

 This is called Big-Oh notation

 There are various Big-Oh categories

 The Big-O notation, O(g(n)), is used to give an upper bound (worst-case) on a