Lets discuss Analysis of Algorithm more informally, so lets start...
This might be a fairy tale. But the point important for us is, how could a simple count like 1,2,4,8.... reach on to some enormously large number? Imagine if you start writing a code which loops once for the first time twice for the second and 4 times for the third iteration, it would be disastrous, YES that is what happens in nuclear explosion. This kind of increase is called EXPONENTIAL.
This shows us that a simple series like this, which looks quite simple might actually deceive us. And if we have two approaches for a same problem selecting one among them we need results in terms of second in time or bytes in memory. But as we know that every person on this earth is unique, so are the computers, the time taken in one machine might be entirely different for the other. Thus a common terminology was introduced which consists of (O,Ω,θ).
big-O: Big-O notation, in general is used to express worst-case scenario or some times average case scenario.
You might have seen people telling Quick-Sort algorithm is better than bubble sort. Since Quick-Sort runs in O(n logn) and bubble sort runs in O(n2). Wait a minute what is this log n for? Where did it come from? Most of the students get worried seeing these terminology, and I was one among them. Let us get those fundamentals in the post 'Analysis of Algorithms 2'
Long long ago, when the chess was invented in India, the king was delighted and asked the inventor to make a wish. And the inventor asked the king to give him few rice grains for which he had a logic, he asked the king to place rice grains in the blocks of chess board. The inventor asked the king to place 1 rice grain in the first block and 2 in the second and 4 int the third block and so on till 64th block ( To be clear the inventor was asking the king to double the rice grains for each block, and give him rice grains of 64th block). The King ordered the Minster to provide the inventor, the requested number of grains.
After few days the inventor returned to the kingdom and informed the king that he din't got the amount of grains, he asked. King immediately asked the minister for reason, to which minister's answers was astonishing. He says even if the whole rice grains cultivated for an year in their kingdom was given to him, it would not suffice.
After few days the inventor returned to the kingdom and informed the king that he din't got the amount of grains, he asked. King immediately asked the minister for reason, to which minister's answers was astonishing. He says even if the whole rice grains cultivated for an year in their kingdom was given to him, it would not suffice.
This might be a fairy tale. But the point important for us is, how could a simple count like 1,2,4,8.... reach on to some enormously large number? Imagine if you start writing a code which loops once for the first time twice for the second and 4 times for the third iteration, it would be disastrous, YES that is what happens in nuclear explosion. This kind of increase is called EXPONENTIAL.
This shows us that a simple series like this, which looks quite simple might actually deceive us. And if we have two approaches for a same problem selecting one among them we need results in terms of second in time or bytes in memory. But as we know that every person on this earth is unique, so are the computers, the time taken in one machine might be entirely different for the other. Thus a common terminology was introduced which consists of (O,Ω,θ).
big-O: Big-O notation, in general is used to express worst-case scenario or some times average case scenario.
You might have seen people telling Quick-Sort algorithm is better than bubble sort. Since Quick-Sort runs in O(n logn) and bubble sort runs in O(n2). Wait a minute what is this log n for? Where did it come from? Most of the students get worried seeing these terminology, and I was one among them. Let us get those fundamentals in the post 'Analysis of Algorithms 2'
No comments:
Post a Comment