Pseudo-polynomial time

Pseudo-polynomial time

An algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input but not necessarily in the length of the input.

Intuition

If you are given an integer input . If you can solve a problem in time we think it is polynomial time algorithm. However the number will be represented in binary so will have length . Therefore the problem running time in the length of the input is .

Examples

• Ford-Fulkerson Algorithm
• Knapsack problem (without repetition)