What are the algorithms?
*, let us consider the problem of cooking maggie. To cook maggie, we need to follow some steps.
Get the utensil.
Get the packet of maggie.
Do we have a packet of maggie?
If yes, start cooking maggie.
Take water in utensil start boiling it.
When water is boiled put maggie and masala in it.
If no, Do we want to buy maggie?
If yes, then go to the market and buy it.
If no, we can drop the plan.
What are we doing in this given problem(cooking maggie), we are providing a step by step procedure for solving it. The formal definition of an algorithm can be defined as:
An algorithm is a step by step unambiguous instructions to solve a given problem.
In the traditional study of algorithms there are two main criteria for judging the merits of algorithms: correctness (does the give solution to the problem in a finite number of steps?) and efficiency (how much resources (in terms of memory and time) does it take to execute the)
(Piece of information: we do not have to prove each step of the algorithm)
Why the Analysis of Algorithms?
To go from city “P” to “Q”, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience, we choose the one that suits us. Similarly, In computer science, multiple algorithms are available to solve the same problem, for example, a sorting problem has many algorithms, like insertion sort, selection sort, quick sort, merge sort and much more. But we cannot use any random algorithm to solve all the problems. We have to check for an efficient one. Analysis of the algorithms helps us to determine which algorithm is our most efficient one in terms of time and space consumed by that algorithm while sorting.
Goals of the analysis of algorithms.
The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g. Memory, developer efforts etc)
What is running Time Analysis?
It is the process of determining how processing time increases as the size of the problems (input size) increases. The input size is the number of elements in the input, and depending on the type of the problems, the input may be of different types. The following are the common types of inputs.
Size of the array.
The number of elements in a matrix.
The number of bits in the binary representation of the input.
Vertices and edges in a graph.
How to Compare Algorithms?
To compare algorithms, let us define a few objective measures.
Not a good measure as execution times are specific to a particular computer.
The number of statements executed?
Not a good measure, since the number of statements, varies with the programming language as well as the style of the individual programmer.
Let us assume that we express the running time of a given as a function of the input size n (i.e., f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc
What is Rate of Growth?
The rate at which the running time increases as a function of input is called the rate of growth. Let us assume that you go to a shop to buy a motorcycle and a bicycle. If your friend sees you there and asks what are you buying, then, in general, you say a motorcycle. This is because the cost of the motorcycle is high compared to the cost of the bicycle (approximating the cost of the bicycle to the cost of the car).
Total Cost = cost_of_motorcylce + cost_of_bicycle
Total Cost ≈ cost_of_motorcycle (approximation)
For the above-mentioned example, we can represent the cost of the car and the cost of the bicycle in terms of function, and 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,
X4 + 4X2 + 50X + 700 ≈ X4
Commonly used Rate Of Growth:
These are some commonly used growth rates.
Time Complexity Name Example
1 Constant Adding an element to the front of a linked list.
Logn Logarithmic Finding an element in a sorted array.
n Linear Finding an element in an unsorted array.
nlogn Linear Logarithmic Sorting in items by ‘divide and conquer’ -Merge Sort
n² Quadratic Shortest path between two nodes in a graph
n³ Cubic Matrix Multiplication
2n Exponential The tower of Hanoi Problem