Algorithm Analysis: Efficiency Measurement Techniques
Classified in Computers
Written on in 
English with a size of 3.14 KB
Problem Solving and Algorithm Goals
There are several ways to solve a problem. How do we choose between them? There are generally two goals in the design of computer programs:
- The design of an algorithm that is easy to understand, codify, and debug (Software Engineering).
- The design of an algorithm that makes efficient use of computer resources (Analysis and Design of Algorithms).
The analysis of algorithms allows us to measure the difficulty of a problem and evaluate the efficiency of an algorithm.
Measuring Execution Time
You cannot measure time in seconds because there is no reference standard computer; instead, we measure the number of basic or elementary operations. The basic operations are performed by the computer in time bounded by a constant, for example:
- Basic arithmetic operations
- Allocation of predefined types
- Jumps (calls to functions, procedures, and return)
- Logical comparisons
- Indexed access basic structures (vectors and matrices)
It is possible to study the complexity of an algorithm based only on a small set of sentences, for example, that influence the runtime.
Methods for Algorithm Execution Time Measurement
To measure the execution time of an algorithm, there are several methods. Some of them are:
a) Benchmarking
The benchmark technique is regarded as a collection of entries representing a typical workload for a program.
b) Profiling
This is to associate each instruction of a program with a number that represents the fraction of the total time taken to execute that particular instruction. One of the best-known techniques (and informal) is the 90-10 rule, which states that 90% of the execution time is spent in 10% of the code.
c) Analysis
This is to group entries according to their size, and estimate the time of execution of the program for entries of that size, T(n). This is the technique to be studied in the course. Thus, the execution time can be defined as a function of the input. Denoted T(n) as the running time of an algorithm for an input of size n.
Asymptotic Efficiency of Algorithms
The main focus of the analysis of algorithms lies in how the execution time grows when the size of the input grows. This is the asymptotic efficiency of the algorithm. It is called "asymptotic" because it analyzes the behavior of functions in the limit, i.e., its growth rate.
Asymptotic Notation
Asymptotic notation is described by a function whose domain is natural numbers (N), estimated from the run time or memory space of algorithms based on the length of the input. Considered asymptotically nonnegative functions. Asymptotic notation captures the behavior of the function for large values of N. The notations are not dependent on the three cases previously seen; that is why a notation that determines the worst case can be present in one or in all situations.