Whenever an algorithm has polynomial complexity, but exponential over the encoding of the input, it is said to be pseudo-polynomial.

What about logarithmic complexity? Wouldn't be wrong to refer to such algorithms as pseudo-polynomial (as often happens)? Shouldn't I instead refer to them as pseudo-logarithmic algorithms?

It seems to me that this latter kind of algorithms are way more efficient and worth to be destinquished. Am I right?

  • 2
    $\begingroup$ You're free to use any term you want, as long as you define it. In some cases a concept already has a name, and in such cases, it's usually a good idea to use it. $\endgroup$ Commented Dec 7, 2021 at 20:31
  • $\begingroup$ Thanks, but I meant something else. I rephrased my question. $\endgroup$ Commented Dec 8, 2021 at 9:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.