(CSC165)_Nov 2_Counting_steps?

Since last week, we begin to learn counting steps. In addition to the surprise that steps are actually harder than I thought  to count, I was actually wondered why that is even relevant.

Counting steps of a simple and brief program actually can be very helpful, because we can get a exact mathematical expression to reveal the relationship between the total steps and the size of input. This can be somehow hard in math, but it turn out to be make me unintentionally begin to realize the importance of efficiency of the algorithm of a program.  Of course, at this moment, in my first year CSC programming course, I may not use a "large" amount of information or data, but in real world the potential amount of data could be huge.

Many online information about this topic show us the length of time increased as a result of different function of the 'steps'. However, the one below very impressive and it is another way to present the issue related to efficiency.

(N1 to N6 represent the size of largest problem can be solved in one hour)

	With present computer	With computer 100 times faster	With computer 1000 times faster
n	N1	100N1	1000N1
n^2	N2	10N2	31.6N2
n^3	N3	4.64N3	10N3
n^5	N4	2.5N4	3.98N4
2^n	N5	N5 + 6.64	N5 + 9.97
3^n	N6	N6 + 4.19	N6 + 6.29

(Reference: M. Garey and D. S. Johnson, 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness)

We can see from the table, for programs with low efficiency, within a limited time, the problem-sovling ability won't really increase noticeably even the computer is 1000 times faster. Therefore,  the technology developing, a focus on efficiency algorithm should necessarily be highlighted, because inefficiency well significantly diminish the result from the faster hardware.