DATA STRUCTURES AND ALGORITHMS:
In the previous article, we saw some basic concepts about Data structures and Algorithms such as What is data structure?, What is Algorithms?, What is an analysis of algorithms? etc
Here, we are going to see a few more interesting concepts of Data structures and Algorithms.
- RATE OF GROWTH
- COMMONLY USED RATE OF GROWTH
- TYPES OF ANALYSIS OF ALGORITHMS
Rate of Growth
“The rate at which the running time increases as a function of input is called rate of growth.”
Let us assume that you go to a shop to buy a PEN and a PENCIL. If your friend sees you there and asks what you are buying, then in general you say buying a PEN. This is because the cost of the PEN is high compared to the cost of the PENCIL (approximating the cost of the PENCIL to the cost of the PEN). For the above-mentioned example, we can represent the cost of the PEN and the cost of the PENCIL in terms of function,
For a given function, ignore the low order terms that are relatively insignificant (for a large value of input size, n). As an example, in the case below, n^4, 2n^ 2, 100n, and 500 are the individual costs of some function and approximate to n^4.
n^4 is the highest rate of growth.
Commonly Used Rates of Growth and Time complexity:
Types of Analysis:
To analyze the given algorithm, we need to know with which inputs the algorithm takes less time (performing well) and with which inputs the algorithm takes a long time. We have already seen that an algorithm can be represented in the form of an expression in growth rate. We represent the algorithm with multiple expressions, one where it takes less time, another where it takes more time.
In general, the first case is called the best case and the second case is called the worst case for the algorithm. To analyze an algorithm we need some kind of syntax, and that forms the base for asymptotic analysis/notation.
There are three types of analysis:
Defines the input for which the algorithm takes a long time (slowest time to complete). Input is the one for which the algorithm runs the slowest.
Defines the input for which the algorithm takes the least time (fastest time to complete). Input is the one for which the algorithm runs the fastest.
Provides a prediction about the running time of the algorithm. Run the algorithm many times, using many different inputs that come from some distribution that generates these inputs, compute the total running time (by adding the individual times), and divide by the number of trials. Assumes that the input is random.
Lower Bound <= Average Time <= Upper Bound
For a given algorithm, we can represent the best, worst and average cases in the form of expressions. As an example, let f(n) be the function that represents the given algorithm. Same for the average case.
The expression defines the inputs with which the algorithm takes the average running time (or memory).