What is the example of polynomial time algorithm Is polynomial time algorithm fastest? Suppose 100 elements in array , then how can I decide algorithm is polynomial time?
Asked
Active
Viewed 2,446 times
0
-
@Miljen Mikic, what should be the value of k , is there any condition for k, not greater than size of array or any? – user Feb 15 '18 at 09:52
-
The exponent `k` should be at least > 0, but in some classifications even >= 1. – Miljen Mikic Feb 15 '18 at 09:54
1 Answers
0
Q: What is the example of polynomial time algorithm?
for (i = 0; i < n; ++i)
printf("%d", i);
This is a linear algorithm, and linear belongs to polynomial class.
Q: Is polynomial time algorithm fastest?
No, logarithmic and constant-time algorithms are asymptotically faster than polynomial algorithms.
Q: Suppose 100 elements in array , then how can I decide algorithm is polynomial time?
You haven't specified any algorithm here, just the data structure (array with 100 elements). However, to determine whether algorithm is polynomial time or not, you should find big-o for that algorithm. If it is O(n^k), then it is polynomial time. Read more here and here.
Miljen Mikic
- 14,765
- 8
- 58
- 66
-
Please note that there are constant polynomials too (mathematically). – Am_I_Helpful Feb 15 '18 at 09:35
-
@Am_I_Helpful You are right, but when speaking about classes of time complexities, usually the exponent should be >= 1 in order that algorithm belongs to the polynomial-time class. Quoting from Wikipedia: "algorithm with time complexity O(n^α) for some constant α ≥ 1 is a polynomial time algorithm." – Miljen Mikic Feb 15 '18 at 09:40