Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in the worst case, $O(p\mathrm{log}(p))$, will it be counted as a poly time algorithm ? Or since $(p\mathrm{log}(p))$ is basically the logarithm of an exponent so it will inefficient. And such an algorithm will be infeasible or intractable. Secondly what if we can cut down the complexity in the worst case scenario to, $O(p\mathrm{log}(p)/5)/100 )$?

Will this complexity be considered same as the worst-case complexity?


As the length of the input is $p$ and the worst case of the algorithm is $O(p\log(p))$, the algorithm is polynomial as the worst case is $O(p^2)$ and $p^2$ is polynomial.

For the second case, there is not any change in time complexity as constant values are multiplied or divided in the polynomial or logarithmic case. To scrutinize more, $p \frac{\log(p/5)}{100} = p \frac{(\log(p) - \log(5))}{100} = \frac{p\log(p) - p\log(5)}{100} = \Theta(p\log(p))$.

  • $\begingroup$ How did you change(approximate) log p into p? Shouldn't log p, be substantially smaller than p? $\endgroup$ – Muhammad Usman Qureshi Oct 8 '18 at 18:32
  • $\begingroup$ It doesn't matter for Big-O. If f is O (p log p) then f is O (p^2), O (p^100), P (p^1.000000001) and many other things. Since you asked "is it considered polynomial time", O (p^2) would be the smallest polynomial (p log p, p^1.1 etc. are not polynomials). $\endgroup$ – gnasher729 Oct 16 '18 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.