Analysing an algorithm is all about predicting the resources the algorithm would need. Usually it is the ‘computational time’ someone is interested. This information though, is critical in choosing an efficient algorithm for your task at hand.
Quiz: What other resources could be there, and what impact can they make?
Generally, the time taken by an algorithm increases with input size, hence the Running Time of an algorithm is described in terms of its input size: Running ‘time’ is simply the total number of steps executed. As an example, for a sorting problem, it is a function of its input…
I grabbed that dust laden, old, fat algorithm book (“Introduction to Algorithms” by Thomas. H. Cormen and others) from the corner of my shelf. I heaved a sigh, in disbelief: “Here I do it again for the umpteenth time!…”. There the cycle restarts once again: I would usually read it past the sorting algorithms in the coming days, and then I would promptly whisk the book away into a forgotten world. Then eons would pass, and the book would collect enough dust in the corner of the shelf before the same ritual will be repeated.
Jeez! What a ‘motivating’ way to start !
The old, fat book says:
“An algorithm is said to be correct if, for every input instance, it halts with the correct output.” — So, a correct algorithm has to halt for any sorts of arrangement of the input. And a correct algorithm has to be correct. (Aha!..Thank you for that piece of information!). Easier said than done, Eh? Let's say, ‘correct’ means the solution respects the problem’s demand. But how do we know that the algorithm is indeed correct, or has solved it, at least? And how long will one have to wait before a program halts? …
The man who forgot what to do