Unit 1_final DESIGN AND ANALYSIS OF ALGORITHM.pdf

Introduction • Algorithm : Step by step procedure for performing some task in finite amount of time • Data Structure :is a systematic way of organizing and accessing data

Methodologies for analyzing algorithm • Determine the running time • Perform several experiments with various size of inputs • Plotting the performance of each run of the algorithm • X- i/p size n • Y-running time

Limitation of experimental model • Experiments can be done only on a limited set of test inputs • Experiments have been performed in the same hardware and software • Solution: • It required analytical framework – Consider all possible inputs – Independent from hardware and software

Pseudo code • Its not an computer program but facilitate the high level analysis of data structure called pseudo code

RAM(Random Access model) • we can define set of primitive operations that are largely independent from the programming language used. • Identified them from the pseudo code • Primitive operations include following: – Assigning a value – Calling a method – Performing an arithmetic operation – Comparing two variables – Indexing in to an array – Object reference – Returning from a method

RAM • Instead of trying to determine the specific execution time of each primitive operation, we will simply count how many primitive operation are executed. • Assumption : the running time of different primitive operations will be same • This approach of simply counting primitive operations give rise to a computational model called RAM

Example • Algorithm: Array max(A,n) • Input: An array A sorting n>=1 integer • Output: The maximum element in A Current max <- A[0] For i<-1 to n-1 do If current max <A[i] then Current max <- A[i] Return current max

Calculation of primitive operations • Initializing the variable current max to A[0] corresponds to two primitive operations. (indexing in to an array and assigning a value) • For loop I initialized to 1 (one primitive operation) • Before entering in to loop , termination condition is checked , i<n (performing n times)

Calculation of primitive operations • For loop executed (n-1) times. – At each iteration two primitive operations required (comparison and indexing) – If this condition is false the total four primitive operations are required (2 (comparison + indexing)+ 2 (i=i+1, assigning and increment)) – If true then (above 4 + 2 (current max <- A[i] , indexing and assigning)) • Therefore body of for loop contributes between 4(n-1) and 6(n-1) units of cost • Returning a value corresponds to one primitive operation

Calculation of primitive operations • At least 2 + 1 +n + 4(n-1) + 1 = 5n • At most 2 + 1 +n + 6(n-1) + 1 = 7n – 2 Best case: T(n)=5n Worst case: T(n)=7n-2

• AlgorithmAverages(X, n) X←new array of nintegers s←0 For i←1 to n−1 do s←s+X[i] s<- s/n Return s

X←new array of nintegers --------------------------1 s←0 --------------------------1 fori←1 to n−1 do ----------------------1 + n s←s+X[i] --------------------5(n-1) s<- s/n --------------------------2 Return s --------------------------1 • Output: 6+5(n-1)+n=6n+1

• In such cases average case analysis would often be valuable, it is typically quite challenging. • It requires to define probability distribution on the set of inputs which is difficult task

How do we compare algorithms? • We need to define a number of objective measures. (1) Compare execution times? Not good: times are specific to a particular computer !! (2) Count the number of statements executed? Not good: number of statements vary with the programming language as well as the style of the individual programmer.

Example • Associate a "cost" with each statement. • Find the "total cost“ by finding the total number of times each statement is executed. Algorithm 1 Algorithm 2 Cost Cost arr[0] = 0; c1 for(i=0; i<N; i++) c2 arr[1] = 0; c1 arr[i] = 0; c1 arr[2] = 0; c1 ... ... arr[N-1] = 0; c1 ----------- ------------- n*c1 n*c2 + (n-1)*c1

Ideal Solution • Express running time as a function of the input size n (i.e., f(n)). • Compare different functions corresponding to running times. • Such an analysis is independent of machine time, programming style, etc.

Asymptotic Analysis • To compare two algorithms with running times f(n) and g(n), we need a rough measure that characterizes how fast each function grows. • Hint: use rate of growth • Compare functions in the limit, that is, asymptotically! (i.e., for large values of n)

Rate of Growth • Consider the example of buying gold and paper: Cost: cost_of_Gold + cost_of_paper Cost ~ cost_of_Gold (approximation) • The low order terms in a function are relatively insignificant for large n n4 + 100n2 + 10n + 50 ~ n4 i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the same rate of growth

Types of Analysis • Worst case – 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 – Provides a lower bound on running time – Input is the one for which the algorithm runs the fastest • Average case – Provides a exact bound on running time – Assumes that the input is random Lower Bound RunningTime Upper Bound  

Asymptotic notations • O-notation

Theorem 1. If d(n) is O(f(n)) then ad(n) is O(f(n)) for any constant a>0. 2. If d(n) is O(f(n)) and e(n) is O(g(n)) then d(n)+e(n) is O(f(n)+g(n)). 3. If d(n) is O(f(n)) and e(n) is O(g(n)) then d(n)e(n) is O(f(n)g(n)). 4. If d(n) is O(f(n)) and f(n) is O(g(n)) then d(n) is O(g(n)).

5. If f(n) is a polynomial of degree k, then f(n) is O(nk) 6. ac is O(1), for any constants c>0 and a>1. 7. log nc is O(log n) for any constant c > 0. 8. logc n is O(nd) for any positive constants c and n.

Examples 2n3 + 4n2log1n =O(n3)

• 2n3 + 4n2log1n =O(n3) Log n=O(n) (rule 8) 4n2= O(n2) (rule 1) 2n3=O(n3) (rule 1) So, finally we have =O(n3)+(O(n)*O(n2)) =O(n3)+O(n3) (rule 3) =O(n3) (rule 1)

• We will prove that 6n2 + 200nlogn + 2 <= 6n2 + 200n2 +2n2 <=208n2 C=208 , n0 >=2

• 5nlog2n n1.5, C=1 and for all n .

• 100n+5=O(n) 100n+5 <= 100n+5n 100n+5 <= 105n c=105 n0>=

Asymptotic notations (cont.) •  - notation (g(n)) is the set of functions with larger or same order of growth as g(n)

Examples – 100n + 5 = (n) 100n+5 >= 100n – C=100 and no>=1

• 5n2 = (n)  5n2 >= n  c = 1 and n0 = 1

Asymptotic notations (cont.) • -notation (g(n)) is the set of functions with the same order of growth as g(n)

More Examples • For each of the following pairs of functions, either f(n) is O(g(n)), f(n) is Ω(g(n)), or f(n) = Θ(g(n)). Determine which relationship is correct. – f(n) = log n2; g(n) = log n + 5 – f(n) = n; g(n) = log n2 – f(n) = log log n; g(n) = log n – f(n) = n; g(n) = log2 n – f(n) = n log n + n; g(n) = log n – f(n) = 10; g(n) = log 10 – f(n) = 2n; g(n) = 10n2 – f(n) = 2n; g(n) = 3n

More Examples • For each of the following pairs of functions, either f(n) is O(g(n)), f(n) is Ω(g(n)), or f(n) = Θ(g(n)). Determine which relationship is correct. – f(n) = log n2; g(n) = log n + 5 – f(n) = n; g(n) = log n2 – f(n) = log log n; g(n) = log n – f(n) = n; g(n) = log2 n – f(n) = n log n + n; g(n) = log n – f(n) = 10; g(n) = log 10 – f(n) = 2n; g(n) = 10n2 – f(n) = 2n; g(n) = 3n f(n) =  (g(n)) f(n) = (g(n)) f(n) = O(g(n)) f(n) = (g(n)) f(n) = (g(n)) f(n) = (g(n)) f(n) = (g(n)) f(n) = O(g(n))

Unit 1_final DESIGN AND ANALYSIS OF ALGORITHM.pdf

More Related Content

Similar to Unit 1_final DESIGN AND ANALYSIS OF ALGORITHM.pdf

Recently uploaded

Unit 1_final DESIGN AND ANALYSIS OF ALGORITHM.pdf