Analysis/Efficiency of Algorithm

Analysis of Algorithm 

• The field of computer science, which studies efficiency of algorithms, is known as analysis of algorithms.
• The time and space used by the algorithm(M) are the two main measures for the efficiency of an algorithm.
• The analysis of algorithms can be evaluated by a variety of criteria. Most often we shall be interested in the rate of growth of the time or space required to solve larger instances of a problem.
• Analysis of the algorithm means solving the problem statement of an algorithm with different approaches.
• Analysis of Algorithm is used to check out for the best algorithm of a problem.
• Algorithm analysis is determination of time, amount of memory utilized and other resources by the system to execute a particular task.
• Analysis of an algorithm performed in two phases: –
  • Prior estimate Analysis:
    • It is concerned with theoretical mathematical calculation that uses asymptotic notations for its representation.
  • Posterior estimate Analysis:
    • It is concerned with writing a program and therefore depends on operating system, compiler, etc.
• Running Time Analysis:
  • The running time analysis of an algorithm is for particular taken input based upon the number of operations executed.
  • The greater the number of operations required, the longer the running time of an algorithm.
  • Running time analysis increases the execution time (number of computational steps) of an algorithm depending on the increase in its input size. When the input size denoted by n, and then the running time of that problem is function f(n).
  • Running time of an algorithm is measured in following steps: –
    (i) By Computing primary functions: Primary functions include instructions with fixed implementation time such as-
         (a) Assignment of variables to objects
         (b) Performing arithmetic operations like addition, subtraction of numbers etc.
         (c) Comparing two values
         (d) Defining a function and calling that function
    (ii) Computing operation of input size n: Growth rate represented in algorithm as function f(n).