In the previous article we had an idea solution for analyzing and comparing algorithms: ” Express the running time of a given algorithm as a function of input size n (i.e. f(n)) ) and compare these different functions “.
To analyze these functions, we will go into some mathematical and graphing concepts.
All of this is the knowledge we have learned since high school and university, when I read it, I found that I had forgotten most of it, but that’s okay, just google search again and you’ll remember it soon
1.8 What is Rate of Growth?
The rate at which the running time increases as a function of input is called rate of growth.
The rate at which running time increases as a function of the input is called Rate of Growth.
A rather abstract concept, let me give an example that people will understand better:
- Let’s say you go to a store to buy a car and a bicycle.
- If your friend sees you there and asks what you’re buying, you’ll generally say buying a car.
- This is because the price of the car is much higher than the price of the bicycle, making the price of the bicycle almost negligible.
1 2 3 4 | Total Cost = cost_of_car + cost_of_bicycle Vì giá của chiếc ô tô là rất lớn so với xe đạp(ví dụ Mercedes AMG 13 tỉ, chiếc xe đạp mini Nhật bãi 300k) => Total Cost ≈ cost_of_car (xấp xỉ) |
For the example mentioned above, we can express the cost of the car and the cost of the bicycle as a function, and for a given function, ignore the relatively insignificant lower orders ( for large value of input size, n) .
For example, in the case below, n^4, 2 * n^2, 100n and 500 are the individual costs of some function and approximate to n^4 because n^4 is the highest rate of change.
1 2 | n^4 + (2 * n^2) + 100n + 500 ≈ n^4 |
1.9 Commonly used Rates of Growth
Below is a list of growth rates that you will encounter in later chapters.
| Time Complexity | Name | For example |
|---|---|---|
| first | Constant | Add a word part to the beginning of a Linked List |
| log n | Logarithmic | Find an element in a sorted array |
| n | Linear | Find an element in an unsorted array |
| n log n | Linear Logarithmic | Sorting n elements using Mergesort . algorithm |
| n^2 | Quadratic | The shortest path between two nodes in the graph |
| n^3 | Cubic | Matrix Multiplication |
| 2^n | Exponential | Tower of Hanoi problem |
The graph below shows the relationship between the different rates of variation.
1.10 Types of Analysis
To analyze the given algorithm, we need to know which input type the algorithm takes less time (performing well) and which input type the algorithm takes longer.
Yeah, this place is a bit confusing, the same algorithm that depends on the input @@ Let me give you an example, the same sorting algorithm Insertion Sort takes maximum time(O(n^2)) to sort. sort if the elements are sorted in reverse order. And it takes the minimum time (O(n)) when the elements are sorted. (I’ll talk more when I come to the chapter on sorting algorithms).
We have also seen that an algorithm can be expressed as an expression.
That means we represent the algorithm with many expressions: one for the case that takes less time and the other for the case that takes more time. .
In general, the first case is called the worst case and the second case is called the good case for the algorithm.
To analyze an algorithm we need some kind of syntax and that forms the basis for asymptotic analysis/notation.
There are three types of analysis:
- Worst case – The worst that can happen
- Determine the input on which the algorithm takes the longest (slowest time to complete).
- Input is the input on which the algorithm runs the slowest.
- Best case – The best case that can happen
- Determine the input that the algorithm takes the least time (fastest time to complete).
- Input is the input on which the algorithm runs the slowest.
- Average case – Average case
- Provides predictions about the running time of the algorithm.
- Run the algorithm multiple times, using different inputs from different sources, calculate the total running time (by adding the individual times) and divide by the number of attempts.
- Assume that the input is random.
1 2 | Lower Bound <= Average Time < Upper Bound |
For a given algorithm, we can represent the best, worst and average cases as expressions. For example, let f(n) be a function, representing the given algorithm.
1 2 3 | f(n) = n^2 + 500 , for worst case f(n) = n + 100n + 500, for best case |
The same goes for the average case.
The expression identifies the inputs on which the algorithm takes the average running time (or memory space).
Ending
The article is quite long, I will stop here, the next post I will detail how we will represent 3 cases with a mathematical function as shown above using symbols. and graphs for illustration.