New types of upper bounds for the smallest size t 2 (2, q ) of a complete arc in the projective plane PG (2, q ) are proposed. The value $${t_{2}(2, q) = d(q)\sqrt{q} \ln q}$$ t 2 ( 2 , q ) = d ( q ) q ln q , where d ( q ) < 1 is a decreasing function of q , is used. The case $${d(q) < \alpha/ \ln{\beta q} + \gamma}$$ d ( q ) < α / ln β q + γ , where $${\alpha,\beta,\gamma}$$ α , β , γ are positive constants independent of q , is considered. It is shown that $$t_{2}(2, q) < (2/\,{\rm ln} \frac{1}{10}q + 0.32)\sqrt{q}\, {\rm ln}\, q\, {\rm if} \, q \leq 67993, q \,{\rm prime}, {\rm and }\, q \in R,$$ t 2 ( 2 , q ) < ( 2 / ln 1 10 q + 0.32 ) q ln q if q ≤ 67993 , q prime , and q ∈ R , where R is a set of 27 values in the region 69997...110017. Also, for $${q \in [9311,67993]}$$ q ∈ [ 9311 , 67993 ] , q prime, and $${q \in R}$$ q ∈ R , it is shown that $$\sqrt{q}({\rm ln}\, q)^{a_1-bq} < t_{2}(2, q) < \sqrt{q}({\rm ln}\, q)^{a_2-bq},$$ q ( ln q ) a 1 - b q < t 2 ( 2 , q ) < q ( ln q ) a 2 - b q , $${a_1=0.771, a_2=0.752, b=2.2 \cdot 10^{-7}.}$$ a 1 = 0.771 , a 2 = 0.752 , b = 2.2 · 10 - 7 . In addition, our results allow us to conjecture that these estimates hold for all q . An algorithm FOP using any fixed order of points in PG (2, q ) is proposed for constructing complete arcs. The algorithm is based on an intuitive postulate that PG (2, q ) contains a sufficient number of relatively small complete arcs. It is shown that the type of order on the points of PG (2, q ) is not relevant.