Engineer bro!

Tue Apr 12 2022 (1 month ago)

Engineer by mistake!

I am a software engineer by passion

What is the analysis of the Algorithm?

The analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity).

History

The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of the search for efficient algorithms.

Why Algorithm analysis is important?

There could be many ways to solve a problem. But we can not use all of them at once, so we need to find the most efficient and appropriate solution. In order to find an efficient solution, we need to analyse all the solutions we have.

As you can see in the above figure, there could be three routes from city A to city D as follows.

1. A->B->D = $23km23km$

2. A->D = $30km30km$

3. A->C->D = $33km33km$

Here, A->B->D = $23km23km$ is the shortest route to travel. In order to find the best routes among all possible routes, we have to analyse the cost of all routes. Then choose the route which has a lower cost.

What if we don't analyse the algorithms?

Suppose we want to sort the names of all people in India in alphabetical order. The population of India is 138 Cr as of now and assume comparing two names will take $O\left(1\right)O\left(1\right)$ (Constant time).

Let's note down the metric we have

• Total names = 138 Cr = 1380000000 $\approx 1{0}^{9}\approx 10^9$

• Comparing names will take $O\left(1\right)O\left(1\right)$

• Computer can execute $1{0}^{9}10^9$ instructions per second.

Consider we have only two sorting algorithms as of now.

Analysing Bubble Sort

Bubble Sort take $O\left({n}^{2}\right)O\left(n^2\right)$ amount of time(instructions) to execute, which means that it'll execute $1{0}^{9}\ast 1{0}^{9}=1{0}^{18}10^9 * 10^9 = 10^\left\{18\right\}$ instructions in total. As our computer is able to execute only $1{0}^{9}10^9$ instructions per second, in order to execute $1{0}^{18}10^\left\{18\right\}$ instruction it'll take $\frac{1{0}^{18}}{1{0}^{9}}=1{0}^{9}\frac\left\{10^\left\{18\right\}\right\}\left\{10^9\right\} = 10^\left\{9\right\}$ seconds.

• Computer can execute $1{0}^{9}10^9$ instructions per second.

• Total instructions that need to be executed is $1{0}^{18}10^\left\{18\right\}$

• Total amount of time needed to execute $1{0}^{18}10^\left\{18\right\}$ instructions on a computer that can execute $1{0}^{9}10^9$ instructions per second will be $\frac{1{0}^{18}}{1{0}^{9}}=1{0}^{9}\frac\left\{10^\left\{18\right\}\right\}\left\{10^9\right\} = 10^\left\{9\right\}$ seconds.

• Total minutes = $\frac{1{0}^{9}}{60}=16666666.66\frac\left\{10^9\right\}\left\{60\right\}=16666666.66$

• Total hours = $\frac{16666666.66}{60}=277777.77\frac\left\{16666666.66\right\}\left\{60\right\}=277777.77$

• Total days = $\frac{277777.77}{24}=11574.07\frac\left\{277777.77\right\}\left\{24\right\}=11574.07$

• Total years = $\frac{11574.07}{365}=31.70\frac\left\{11574.07\right\}\left\{365\right\}=31.70$

Can you believe, that even a computer needs ~31 years to sort all names of great India?

Analysing Merge Sort

Merge Sort take $O\left(n\mathrm{log}n\right)O\left(n \log n\right)$ amount of time(instructions) to execute, which means that it'll execute $1{0}^{9}\ast \left(\mathrm{log}1{0}^{9}\right)=1{0}^{9}\ast 29.89=29300000000=1{0}^{1}010^9 * \left(\log10^9\right) = 10^9*29.89=29300000000=10^10$ instructions in total. As our computer is able to execute only $1{0}^{9}10^9$ instructions per second, in order to execute $1{0}^{1}010^10$ instruction it'll take $\frac{1{0}^{10}}{1{0}^{9}}=10\frac\left\{10^\left\{10\right\}\right\}\left\{10^9\right\} = 10$ seconds.

You can see ~31 year problem can be solved in just 10 seconds by just choosing efficient algorithms.

Conclusion

We have to see what is the analysis of the algorithm and why analysis is important.

AlgorithmsData StructureDesign And Analysis of Algorithms