Engineer bro!
Tue Apr 12 2022 (1 month ago)
Engineer by mistake!
I am a software engineer by passion
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).
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.
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.
A->B->D = $$23km23km$$
A->D = $$30km30km$$
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.
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).
Total names = 138 Cr = 1380000000 $$\approx 1{0}^{9}\backslash approx\; 10^9$$
Comparing names will take $$O(1)O(1)$$
Computer can execute $$1{0}^{9}10^9$$ instructions per second.
Consider we have only two sorting algorithms as of now.
Bubble Sort take $$O({n}^{2})O(n^2)$$ 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^\{18\}$$ 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^\{18\}$$ instruction it'll take $$\frac{1{0}^{18}}{1{0}^{9}}=1{0}^{9}\backslash frac\{10^\{18\}\}\{10^9\}\; =\; 10^\{9\}$$ seconds.
Computer can execute $$1{0}^{9}10^9$$ instructions per second.
Total instructions that need to be executed is $$1{0}^{18}10^\{18\}$$
Total amount of time needed to execute $$1{0}^{18}10^\{18\}$$ 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}\backslash frac\{10^\{18\}\}\{10^9\}\; =\; 10^\{9\}$$ seconds.
Total minutes = $$\frac{1{0}^{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?
Merge Sort take $$O(n\mathrm{log}n)O(n\; \backslash log\; n)$$ amount of time(instructions) to execute, which means that it'll execute $$1{0}^{9}\ast (\mathrm{log}1{0}^{9})=1{0}^{9}\ast 29.89=29300000000=1{0}^{1}010^9\; *\; (\backslash log10^9)\; =\; 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\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.
We have to see what is the analysis of the algorithm and why analysis is important.
© 2021 dsabyte. All rights reserved
Comments (0)