Algorithmic Complexity

Share |

The academic field and engineering practice of computer programming are largely concerned with discovering and implementing the most efficient algorithms for a given class of problem. For this purpose, algorithms are classified into orders using so-called Big O notation, O(n), which expresses execution time, memory consumption, or another parameter in terms of the size of an input. Expert programmers are familiar with a variety of well-established algorithms and their respective complexities, and use this knowledge to consider design trade-offs between, for example, memory consumption and performance.

Research in computer programming includes investigation into the unsolved proposition that P, the class of algorithms which can be deterministically solved in polynomial time with respect to an input, is not equal to NP, the class of algorithms for which no polynomial-time solutions are known. Work has shown that many NP algorithms can be transformed, in polynomial time, into others, such as the Travelling salesman problem, thus establishing a large class of "hard" problems which are for the purposes of analysis, equivalent.