2.1 Computational Tractability

Efficiency of algorithms is defined in the terms of the running time and the algorithms must be efficient in their use of other resources as well, especially the amount of space(or memory) they use. To analyze algorithms, we focus on the worst case running time where we look for a bound on the largest possible running time the algorithm could have over all inputs of a given size N, and see how it scales with N. The worst-case analysis is the best used when analyzing algorithms. An efficient algorithm is an algorithm that is platform-independent, instance-independent and has predictive value with respect to increasing input sizes. Such an algorithm must achieve qualitatively better worst-case performance at an analytical level than brute-force search. Suppose for a given algorithm, there are absolute constants c > 0 and d >0 so that on every input of size N, its running time is bounded by cN^d primitive computational steps.This means that its running time is at most proportional to N ^d. If this running-time bound holds, for some c and d,then the algorithm has a polynomial running time and is called a polynomial-time algorithm. We define an efficient algorithm as an algorithm that has a polynomial running time.</sup>