What is Algorithm Analysis? - Methods & Types

Instructor: Meghalee Goswami

Meghalee has a masters of computer science and communication engineering.

This lesson explains algorithm analysis and the various ways of doing it. It also describes the difference between experimental and asymptotic analysis and also discusses the limitations of experimental analysis.

Algorithm Analysis

An algorithm analysis is a technique that is used to measure the performance of the algorithms. Speed is one of the key parameters in determining the potential of an algorithm. There are some other factors like user-friendliness, security, maintainability, and usage space that determine the quality of an algorithm. Space and time complexity are metrics used to measure parameters.

Experimental Analysis of Algorithms

Every algorithm gives an output based on some parameters like the number of loops, sample input size, and various others. In an experimental analysis, these data points are plotted on a graph to understand the behavior of the algorithm. We consider the worst-case running times. The graphs show the running time of an algorithm with increasing input size for worst, average, and best case running time in the form of a histogram and a plotted graph. We chose the x-axis as the input size because the running time depends on the input size. As an experimental analysis depends on the output results, an algorithm cannot be measured unless an equivalent program is implemented.

Experimental Analysis Histogram - Input Size
Experimental Analysis - Input Size

Experimental Analysis - Running Time
Experimental Analysis - Running Time

Limitations of Experimental Studies

The limitations of experimental analysis include:

  • Implementing algorithms can be a tedious process
  • Hardware and software environments must be the same to compare algorithms (which is practically impossible).
  • Input samples may not cover all the possible inputs and scenarios

Asymptotic analysis

In order to overcome the constraints associated with experimental analysis, a set of mathematical notations were introduced to understand the run-time performances of algorithms. This is a theoretical analysis based so it doesn't require actual implementation. The upper bound is a measure of the worst case or maximum time taken to run an algorithm when represented graphically. The lower bound measures the best case or minimum time taken. There are three main types of asymptotic notations.

  • Big Oh (O)
    • Measures the upper bound (worst case or maximum time)
    • For an algorithm represented by f(n) where n is the input size, O(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }, where g(n) is the upper bound calculated.

Big Oh

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account