In computational complexity theory<http://en.wikipedia.org/wiki/Computational_complexity_theory>, a numeric algorithm runs in *pseudo-polynomial time* if its running time<http://en.wikipedia.org/wiki/Computation_time> is polynomial <http://en.wikipedia.org/wiki/Polynomial> in the *numeric value* of the input (which is exponential in the *length* of the input – its number of digits).
For instance, the dynamic programming algorithm for knapsack problems runs O(nW), n is the number of objects and W is capacity of knapsack. the ford-fulkerson algorithm runs O(Ef) where [image: E] is the number of edges in the graph and [image: f] is the maximum flow in the graph, The complexity of algorithm depends of numeric value W (knapsack) e f (ford-fulkerson algorithm) Wladimir Araujo Tavares *Federal University of Ceará <http://lia.ufc.br/%7Ewladimir/> Homepage <http://lia.ufc.br/%7Ewladimir/> | Maratona<https://sites.google.com/site/quixadamaratona/>| * On Mon, Nov 5, 2012 at 4:23 AM, Milan Jain <[email protected]> wrote: > Pseudo polynomial run time algorithm are the algorithm that are having > running time polynomial in the value of input and polynomial time > algorithms are having running time polynomial in length of input. > For example, If an algorithm is having running time O(n) and n is the > value of the input like 1,2,3...etc. It is pseudo polynomial and O(t) where > t=|n|, now algorithm is having run time polynomial time. > > > On Mon, Nov 5, 2012 at 4:41 AM, pranav shah <[email protected]>wrote: > >> Guys I want to understand the difference in between these two terms. >> >> 1. Pseudo Polynomial run time algorithm >> 2.Polynomial run time algorithm >> >> (Please give example and explain) I googled but had very few reference >> sites, so I am not clear on it. >> >> Pranav >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msg/google-code/-/v_BuHs5ViW4J. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
