Fundamentals of the Analysis of Algorithm Efficiency

Fundamentals of the Analysis of Algorithm Efficiency

• 1.
  Fundamentals of theAnalysis of Algorithmic Efficency
• 2.
  ANALYSIS FAMEWORK Efficiency ofan algorithm can be in terms of time or space. Thus, checking whether the algorithm is efficient or not means analyzing the algorithm. There is a systematic approach that has to be applied for analyzing any given algorithm. This systematic approach is modelled by a framework called as ANALYSIS FRAMEWORK. The efficiency of an algorithm can be decided by measuring the performance of an algorithm.
• 3.
  Analysis of algorithmis the process of investigation of an algorithm’s efficiency respect to two resources: I. Running time II. Memory space The reason for selecting these two criteria are  Simplicity  Generality  Speed  Memory
• 4.
  Time efficiency ortime complexity indicates how fast an algorithm runs. Space Efficiency or space complexity is the amount of memory units required by the algorithm including the memory needed for the i/p & o/p
• 5.
  ANALYSIS OF ALGORITHMS Analysisof algorithms Measuring time complexity Computing best,worst and average case efficiencies Measuring Input size Measuring running time Computing order of growth of algorihtms Measuring space complexity
• 6.
  Space complexity The amountof memory required by an algorithm to run. To Compute the space complexity we use two factors: constant and instance characteristic S(p) = C + Sp C – Constant -> space taken by instruction, variable and identifiers Sp – space dependent upon instance characteristic For eg: add(a,b) return a+b S(p) = C + Sp S(p)=C+0 a,b occupy one word size then total size come to be 2
• 7.
  Time complexity The amountof time required by an algorithm to run for completion. For instance in multiuser system , executing time depends on many factors such as: System load Number of other programs running Instruction set used Speed of underlying hardware Frequency count is a count denoting number of times of execution of statement
• 8.
  For eg: Calculatingsum of n numbers For(i=0;i<n;i++) { Sum=sum+a[i]; } Statement Frequency count i=0 1 i<n N+1 i++ n Sum=sum+a[i] n Total 3n+2 Time complexity normally denotes in terms of Oh notation(O). Hence if we neglect the constants then we get the time complexity to be O(n)
• 9.
  Eg: Matrics addition For(i=0;i<n;i++) { for(j=0;j<n;j++) { c[i][j]=a[i][j]+b[i][j] } }
• 10.
  The frequency countis: Statement Frequency count i=0 1 i<n N+1 i++ n j=0 N * 1 = n For Initialization Outer loop of j j<n N * (n+1) =n2 + n times For Outer loop j++ n * n = n2 C[i][j]=a[i][j]+b[i][j] n * n = n2 Total 3n2 +4n+2 O(n2 )
• 11.
  Measuring an Inputsize:  Efficiency measure of an algorithm is directly proportional to the input size or range  So an alg efficiency could be measured as a function of n, where n is the parameter indicating the algorithm i/p size.  For ex: when multiplying two matrices, the efficiency of an alg depends on the no. of multiplication performed not on the order of matrices.  The i/p given may be a square or a non-square matrix.  Some algortihm require more than one parameter to indicate the size of their i/p  In such situation, the size is measured by the number of bits in the n’s binary representation: B=floor(log2 n+1)
• 12.
  Eg: Sorting Naive Algorithm –n2 Best Algorithm – nlogn
• 13.
  Units for measuringRunning time The running time of an alg depends on:  Speed of a particular computer  Quality of a program  Compiler used To measure the alg efficiency: Identify the important operation(core logic) of an algorithm. This operation is called basic operation So compute the no. of times the basic operation is executed will give running time Basic operation mostly will be in inner loop, it is time consuming
• 14.
  Problem statement Inputsize Basic operation Searching a key element from the list of n elements List of n elements Comparison of key with every element of list Perform matrix multiplication The two matrices with order n x n Actual multiplication of the elements in the matrices Computing GCD of two numbers Two numbers Division
• 15.
  Using the formulathe computing time can be obtained T(n)=Cop C(n) Running time of basic operation Execution time of the basic operation Number of times the operation needs to be executed
• 16.
  Order of growth
• 17.
  Rate of growthof common computing time function
• 18.
  Worst case, Bestcase and Average case Efficiency An Algortihm efficiency is measured as a function of a parameter indicating the size of the alg’s i/p But some algortihm for which running time depends in i/p size and on the particular i/p.
• 19.
  Time space Tradeoff Timespace tradeoff is basically a situation where either a space efficiency can be achieved at the cost of time or a time efficiency can be achieved at the cost of memory