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).

Table of contents

• History

• Why Algorithm analysis is important?

• What if we don't analyse the algorithms?

  • Let's note down the metric we have

  • Analysing Bubble Sort

  • Analysing Merge Sort

• Conclusion

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(1)O(1)$$ (Constant time).

Let's note down the metric we have

• Total names = 138 Cr = 1380000000 $$\approx 10^9\backslash approx\; 10^9$$

• Comparing names will take $$O(1)O(1)$$

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

Consider we have only two sorting algorithms as of now.

Analysing Bubble Sort

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

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

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

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

• Total minutes = $$\frac{10^9}{60}=16666666.66\backslash frac\{10^9\}\{60\}=16666666.66$$

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

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

• Total years = $$\frac{11574.07}{365}=31.70\backslash frac\{11574.07\}\{365\}=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(n\log n)O(n\; \backslash log\; n)$$ amount of time(instructions) to execute, which means that it'll execute $$10^9\ast (\log 10^9)=10^9\ast 29.89=29300000000=10^{1}010^9\; *\; (\backslash log10^9)\; =\; 10^9*29.89=29300000000=10^10$$ instructions in total. As our computer is able to execute only $$10^{9}10^9$$ instructions per second, in order to execute $$10^{1}010^10$$ instruction it'll take $$\frac{10^{10}}{10^9}=10\backslash frac\{10^\{10\}\}\{10^9\}\; =\; 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.