- #1

- 1

- 0

## Main Question or Discussion Point

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