Analysis of Algorithm

Pseudo polynomial Algorithms

pseudo polynomial algorithms
pseudo polynomial Algorithms - Analysis of Algorithm - An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs)

What is Pseudo polynomial?

An pseudo polynomial Algorithms whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo polynomial algorithm.

For example, Consider the problem of counting frequencies of all elements in an array of positive numbers. A pseudo polynomial time solution for this is to first find the maximum value, then iterate from 1 to maximum value and for each value, find its frequency in array. This solution requires time according to maximum value in input array, therefore pseudo polynomial. On the other hand, an algorithm whose time complexity is only based on number of elements in array (not value) is considered as polynomial time algorithm.

Pseudo polynomial and NP-Completeness

Some NP-Complete problems have Pseudo Polynomial time solutions.

For example, Dynamic Programming Solutions of 0-1 Knapsack, Subset-Sum and Partition problems are Pseudo Polynomial. NP complete problems that can be solved using a pseudo polynomial time algorithms are called weakly NP-complete.

About the author

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment