ANALYSIS OF ALGORITHM
CSE-237 : ALGORITHM DESIGN AND ANALYSIS
WHY STUDY ALGORITHMS?
• Necessary in any computer programming problem
✔ Improve algorithm efficiency: run faster, process more data, do something that would
otherwise be impossible
✔ Solve problems of significantly large size
✔ Technology only improves things by a constant factor
• Compare algorithms
Analysis of Algorithm ‹#›
WHY STUDY ALGORITHMS? .....
• Algorithms as a field of study
✔ Learn about a standard set of algorithms
✔ New discoveries arise
✔ Numerous application areas
• Learn techniques of algorithm design and analysis
Analysis of Algorithm ‹#›
ANALYZING ALGORITHMS
• Predict the amount of resources required:
✔ Memory : How much space is needed?
✔ Computational Time : How fast the algorithm runs?
✔ Numerous application areas
• FACT : Running time grows with the size of the input
Analysis of Algorithm ‹#›
ANALYZING ALGORITHMS ....
• Predict the amount of resources required:
✔ Memory : How much space is needed?
✔ Computational Time : How fast the algorithm runs?
✔ Numerous application areas
• FACT : Running time grows with the size of the input
• Input size (number of elements in the input)
• Learn techniques of algorithm design and analysis
Analysis of Algorithm ‹#›
APPLICATIONS
• Multimedia • Computers
✔ CD player, DVD, MP3, JPG, DivX, HDTV ✔ Circuit layout, file systems
• Internet • Science
✔ Packet routing, data retrieval (Google) ✔ Human genome
• Communication • Transportation
✔ Cell-phones, e-commerce
✔ Airline crew scheduling, ARAMEX and
DHL deliveries
Greedy Algorithms 6
ROADMAP
• Different problems
✔ Searching
✔ Sorting
✔ Graph problems
• Different design paradigms
✔ Divide-and-conquer
✔ Greedy algorithms
✔ Dynamic programming
Analysis of Algorithm 7
ANALYZING ALGORITHMS
• Predict the amount of resources required:
✔ Memory : How much space is needed?
✔ Computational Time : How fast the algorithm runs?
✔ Numerous application areas
• FACT : Running time grows with the size of the input
Analysis of Algorithm ‹#›
ANALYZING ALGORITHMS ....
• Input size (number of elements in the input) :
✔ size of an array, polynomial degree, # of elements in a matrix, # of bits in the binary
representation of the input, vertices and edges in a graph
• Running time : the number of primitive operations (steps) executed before termination
✔ Arithmetic operations (+, -, *), data movement, control, decision making (if, while),
comparison
Analysis of Algorithm ‹#›
ALGORITHM EFFICIENCY VS SPEED
Problm : Sorting n numbers Computer Algorithm
(Instructions/Second) (Instructions)
6 Friends 109 2n2
Sort 10 numbers!
Your 107 50nlgn
2000/100 = 20
times better!!
Analysis of Algorithm ‹#›
ALGORITHM ANALYSIS: EXAMPLE
• Running time:
MIN (a[1], …, a[n]) • the number of primitive operations (steps) executed
before termination
m ← a[1];
T(n) =1 [first step] + (n) [for loop] + (n-1) [if condition] +
for i ← 2 to n
if a[i] < m then (n-1) [the assignment in then] = 3n - 1
m ← a[i]; • Order (rate) of growth:
• The leading term of the formula
• Expresses the asymptotic behavior of the algorithm
Analysis of Algorithm ‹#›
TYPICAL RUNNING TIME FUNCTIONS
• 1 (constant running time):
✔ Instructions are executed once or a few times
• logN (logarithmic)
✔ A big problem is solved by cutting the original problem in smaller sizes, by a constant fraction
at each step
• N (linear)
✔ A small amount of processing is done on each input element
• N logN
✔ A problem is solved by dividing it into smaller problems, solving them independently and
combining the solution
Analysis of Algorithm 12
TYPICAL RUNNING TIME FUNCTIONS ....
• N2 (quadratic)
✔ Typical for algorithms that process all pairs of data items (double nested loops)
• N3(cubic)
✔ Processing of triples of data (triple nested loops)
• NK (polynomial)
• 2N (exponential)
✔ Few exponential algorithms are appropriate for practical use
Analysis of Algorithm 13
PRACTICAL COMPLEXITY
Analysis of Algorithm 14
PRACTICAL COMPLEXITY ....
Analysis of Algorithm 15
PRACTICAL COMPLEXITY ....
Analysis of Algorithm 16
WHY DO WE NEED FASTER ALGORITHMS?
Analysis of Algorithm 17
ASYMPTOTIC NOTATIONS
• A way to describe behavior of functions in the limit
▪ Abstracts away low-order terms and constant factors
▪ How we indicate running times of algorithms
▪ Describe the running time of an algorithm as n grows to ∞
• O notation : asymptotic “less than and equal”
f(n) “≤” g(n)
• Ω notation : asymptotic “greater than and equal”
f(n) “≥” g(n)
• Θ notation : asymptotic “equality” f(n) “=” g(n)
Analysis of Algorithm 18
ASYMPTOTIC NOTATIONS - EXAMPLES
• Θ notation
– n2/2 – n/2 = Θ
(n+2)1)
– (6n3 + 1)lgn/(n = Θ
2
– n vs. n2 n ≠ Θ (n lgn)
• Ω notation (n2)
• O notation
– n3 vs. n2 n3 = Ω – 2n2 vs. n3 2n2 = O(n3)
– n vs. logn (n2) – n2 vs. n2
n = Ω n2 = O(n2)
– n vs. n2 (logn)
n ≠ Ω – n3 vs. nlogn n3 ≠
(n2) O(nlgn)
Analysis of Algorithm 19
RECURSIVE ALGORITHMS
Binary search : for an ordered array A, finds if x is in the array A[lo…hi]
BINARY-SEARCH (A, lo, hi, x) 1 2 3 4 5 6 7 8
if (lo > hi)
2 3 5 7 9 10 11 12
return FALSE
mid ← ⎣(lo+hi)/2⎦ mid
if x = A[mid] lo hi
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)
Analysis of Algorithm 20
RECURRENCES
• Recurrence is an equation or inequality that describes a function in terms of its value
on smaller inputs, and one or more base cases
▪ E.g.: T(n) = T(n-1) + n
• Useful for analyzing recurrent algorithms
• Methods for solving recurrences
▪ Iteration, Substitution, Recursion Tree and Master methods
Analysis of Algorithm 21
SORTING
Iterative methods
• Insertion sort
• Bubble sort
• Selection sort
Divide and conquer Non-comparison methods
• Merge sort • Counting sort
• Quicksort • Radix sort
• Bucket sort
Analysis of Algorithm 22
TYPES OF ANALYSIS
• Worst case ( e.g. data reversely ordered )
▪ Provides an upper bound on running time
▪ An absolute guarantee that the algorithm would not run longer, no matter what the inputs are
• Best case ( e.g. data already ordered )
▪ Input is the one for which the algorithm runs the fastest
• Average case ( e.g. general case )
▪ Provides a prediction about the running time
▪ Assumes that the input is random
Analysis of Algorithm 23
GREEDY ALGORITHM
Explore it on NEXT DAY
