How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program?

Is there any other way to decide?

  • $\begingroup$ Empirical determination of the asymptotic behavior of a program is not really possible. $\endgroup$
    – user16034
    Commented Jan 3, 2023 at 10:43

1 Answer 1


You can't. "Polynomial time" is a statement about asymptotics. Observing the running time on various finite values of the input size can't tell you the asymptotic running time.

See How to fool the plot inspection heuristic?.

  • $\begingroup$ How to decide between polynomial and fully polynomial approximation algorithm according to relative error? As "The running time of PTAS must be polynomial in terms of n, however, it can be exponential in terms of ε. In PTAS algorithms, the exponent of the polynomial can increase dramatically as ε reduces, for example if the runtime is O(n(1/ε)!) which is a problem. There is a stricter scheme, Fully Polynomial Time Approximation Scheme (FPTAS). In FPTAS, algorithm need to polynomial in both the problem size n and 1/ε." $\endgroup$
    – SAbeA
    Commented Aug 11, 2021 at 10:22
  • $\begingroup$ Observing runtime is useful to make a guess about the asymptotic behaviour and what kind of asymptotic behaviour you will be trying to prove. On the other hand, it may be difficult to decide whether Quicksort might be O(n) or O(n log n) or O(n^1.1) based on a small number of observations. $\endgroup$
    – gnasher729
    Commented Jan 3, 2023 at 9:25

Your Answer

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

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