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

Table of contents

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.
Why Algorithm analysis is important?

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 109\approx 10^9

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

  • Computer can execute 10910^9 instructions per second.

Consider we have only two sorting algorithms as of now.

Bubble sort and merge sort

Analysing Bubble Sort

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

  • Computer can execute 10910^9 instructions per second.

  • Total instructions that need to be executed is 101810^{18}

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

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

  • Total hours = 16666666.6660=277777.77\frac{16666666.66}{60}=277777.77

  • Total days = 277777.7724=11574.07\frac{277777.77}{24}=11574.07

  • Total years = 11574.07365=31.70\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(nlogn)O(n \log n) amount of time(instructions) to execute, which means that it'll execute 109(log109)=10929.89=29300000000=101010^9 * (\log10^9) = 10^9*29.89=29300000000=10^10 instructions in total. As our computer is able to execute only 10910^9 instructions per second, in order to execute 101010^10 instruction it'll take 1010109=10\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.

AlgorithmsData StructureDesign And Analysis of Algorithms

Comments (0)

Discussions (0)


© 2021 dsabyte. All rights reserved