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?
1
-
$\begingroup$ Empirical determination of the asymptotic behavior of a program is not really possible. $\endgroup$– Yves DaoustJan 3 at 10:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\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$– SAbeAAug 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$ Jan 3 at 9:25