Polynomial vs. Exponential Running Time

Post date: Nov 1, 2013 8:49:04 AM

< Previous-Asymptotic Notations Next - Divide and Conquer Technique>

The time complexity(generally referred as running time) of an algorithm is expressed as the amount of time taken by an algorithm for some size of the input to the problem. Big O notation is commonly used to express the time complexity of any algorithm as this suppresses the lower order terms and is described asymptotically. Time complexity is estimated by counting the operations(provided as instructions in a program) performed in an algorithm. Here each operation takes a fixed amount of time in execution. Generally time complexities are classified as constant, linear, logarithmic, polynomial, exponential etc. Among these the polynomial and exponential are the most prominently considered and defines the complexity of an algorithm. These two parameters for any algorithm are always influenced by size of input.

Polynomial Running Time

An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k) for some non-negative integer k, where n is the complexity of the input. Polynomial-time algorithms are said to be "fast." Most familiar mathematical operations such as addition, subtraction, multiplication, and division, as well as computing square roots, powers, and logarithms, can be performed in polynomial time. Computing the digits of most interesting mathematical constants, including pi and e, can also be done in polynomial time.

Ref:WolframMathWorld

All basic arithmetic operations ((i.e.) Addition, subtraction, multiplication,division), comparison operations, sort operations are considered as polynomial time algorithms.

Exponential Running Time

The set of problems which can be solved by an exponential time algorithms, but for which no polynomial time algorithms is known. An algorithm is said to be exponential time, if T(n) is upper bounded by 2^poly(n), where poly(n) is some polynomial in n. More formally, an algorithm is exponential time if T(n) is bounded by O(2^nk) for some constant k.Ref:Wiki

Examples of exact Exponential time algorithms can be read from following link of Computer Science Algorithms

Algorithms which have exponential time complexity grow much faster than polynomial algorithms. The difference you are probably looking for happens to be where the variable is in the equation that expresses the run time. Equations that show a polynomial time complexity have variables in the bases of their terms. Examples: n³ + 2n² + 1. Notice n is in the base, NOT the exponent. In exponential equations, the variable is in the exponent. Examples: 2ⁿ. As said before, exponential time grows much faster. If n is equal to 1000 (a reasonable input for an algorithm), then notice 1000³ is 1 billion, and 2¹⁰⁰⁰ is simply huge! For a reference, there are about 2⁸⁰ hydrogen atoms in the sun, this is much more than 1 billion.

for more reference you can check this PDF file

< Previous-Asymptotic Notations Next - Divide and Conquer Technique>