When designing digital systems, the problem of optimizing the area and performance of finite state machines (FSMs) often arises. Known methods of FSM synthesis and state encoding usually use only one estimate of the area or performance. However, regardless of the computational complexity of the synthesis or state encoding method, if the estimate does not correctly reflect the optimization objective, the result will significantly differ from the optimal solution. This paper discusses several FSM area and performance estimates, which can be divided into the FPGA, terms, CPLD, ASIC, and dec classes. The FPGA, terms, CPLD, and ASIC class estimates determine the FSM area and consider the electronic element in which the FSM is implemented (FPGA, CPLD, or ASIC). The dec class estimates determine the FSM performance and consider the Boolean function decomposition method used by the design tool. This paper investigates the computational complexity of the proposed estimates based on the expressions and algorithms to compute them. Experimental studies on benchmark showed that the computational complexity of the different estimates differed by no more than 21.4%. Recommendations on the practical use of the proposed estimates are also given. The Conclusion outlines promising directions for future research.