An algorithm can be defined as a set of step-by-step instructions which govern the outline of a program that needs to be executed using computational resources. The execution can be in any programming language such as R, Python, and Java. Data is an intricate component of any program, and depending on how data is organized (data structure), your execution time can vary drastically. That's why data structure is such a critical component of any good algorithm implementation. This book will concentrate primarily on running time or time complexity and partly on memory utilization and their relationship during program execution. The current chapter will cover following topics in detail:
- Best, worst, and average cases
- Computer versus algorithm
- Algorithm asymptotic analysis
- Upper bounds evaluation
- Lower bounds evaluation
- Big Θ notation
- Simplifying rules
- Classifying functions
- Computation evaluation of a program
- Analyzing problems
- Space bounds
- Empirical analysis
Data structure is a critical component in any algorithm. Before we go into details; let's illustrate this with an example; a sorting algorithm for positive integer for a finite length needs to be programmed using user input, and the output is to be displayed in ascending order. The sorting algorithm, which acts as a connector between the user-defined input and user-desired output can be approached in multiple ways:
- Bubble sort and shell sort, which are simple variants of sorting, but are highly inefficient
- Insertion sort and selection sort, primarily used for sorting small datasets
- Merge sort, heap sort, and quick sort, which are efficient ways of sorting based on the complexities involved in an average system runtime
- Distributed sorts such as counting sort, bucket sort, and radix sort, which can handle both runtime and memory usage
Each of these options can, in turn, handle a particular set of instances more effectively. This essentially reduces the concept of good algorithm. An algorithm can be termed as good if it possesses attributes such as the following among many others:
- Shorter running time
- Lesser memory utilization
- Simplicity in reading the code
- Generality in accepting inputs
In general, a problem can be approached using multiple algorithms, and each algorithm can be assessed based on certain parameters such as:
- System runtime
- Memory requirement
However, these parameters are generally affected by external environmental factors such as:
- Handling of data structures
- System software and hardware configurations
- Style of writing and compiling codes
- Programming language
As it is almost impossible to control all external parameters, it becomes difficult to estimate the system runtime of multiple algorithms for performance comparison (ideal scenario analysis). Ideal scenario analysis requires algorithms to be implemented and executed for evaluating algorithm performance. However, in a scenario where the user is trying to design an algorithm, asymptotic analysis is utilized to evaluate algorithm performance.
Asymptotic analysis assesses algorithm's efficiency without actually coding and compiling the entire program. It is a functional form representing pseudo system runtime based on the size of input data and number of operations. It is based on the principle that the growth rate of input data is directly proportional to the system runtime. For example, in the case of insertion sorting, the size represents the length of the input vector, and the number of operations represents the complexity of sort operations. This analysis can only be used to gauge the consideration of implementing the algorithm rather than evaluating the comparative merits and demerits of algorithms. The following table represents the most widely used growth rate functional forms. The details are mentioned in later parts of the chapter.
Figure 2.1: Different growth rate functional form used for complexity evaluation
The most widely used functional forms of growth rates are based on the size of input data, which are used to analyze the performance of algorithms. These are also considered as pseudo-functional forms to evaluate algorithm's system runtime.