Is it Polynomial time algorithm

Question

If an algorithm's input size is 2^n and the algorithm runs in $O(n2^n)$ time. In this case, can we say that the algorithm runs in polynomial time with respect to input size?

David Eisenstat · Accepted Answer · 2017-01-27 14:49:55Z

6

Yes, that would be an O(k log k)-time algorithm, where k = 2^n.

answered Jan 27, 2017 at 14:49

David Eisenstat

65.7k7 gold badges66 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

NARAYAN CHANGDER Over a year ago

Thanks, @David So, I could say it is a polynomial time or pseudopolynomial? I am confused between these two.

Codor Over a year ago

A good question and a good answer - everything depends on the right definitions; I always found it somewhat puzzling that, for instance, for matrix multiplication algorithms, the runtime bound is usually stated in terms of n where the input is of size n*n.

David Eisenstat Over a year ago

@NARAYANCHANGDER Polynomial. An example of a pseudopolynomial running time is O(k^log k).

Collectives™ on Stack Overflow

Is it Polynomial time algorithm

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related