- #1
mourinho123
- 1
- 0
Greetings,
This is very simple, and obviously I'm missing something trivial, but I still don't get it.
An algorithm is said to run in polynomial time if it runs in O(n^K) time.
That's why dijkstra for example, who runs in O(V^2), runs in polynomial time.
That said, my doubt is the following:
If a brute-force trial division primality check algorithm, runs in O(n^(1/2)), why it isn't considered in polynomial time?
Thanks beforehands,
Mourinho
This is very simple, and obviously I'm missing something trivial, but I still don't get it.
An algorithm is said to run in polynomial time if it runs in O(n^K) time.
That's why dijkstra for example, who runs in O(V^2), runs in polynomial time.
That said, my doubt is the following:
If a brute-force trial division primality check algorithm, runs in O(n^(1/2)), why it isn't considered in polynomial time?
Thanks beforehands,
Mourinho