Opacity is a security property of discrete-event systems that asks whether, at any point of a computation, the secret is revealed to a passive intruder. The literature has introduced several notions of opacity, including language-based opacity, trace opacity, current-state opacity, weak k-step opacity, weak infinite-step opacity, strong k-step opacity, initial-state opacity, and initial-and-final-state opacity. In this work, we provide a complete and improved complexity picture of verifying the discussed opacity notions within the finite automata model. First, we focus on the complexity of deciding current-state opacity in systems with a restricted set of events and a restricted structure. Second, we present polynomial-time transformations among the notions that preserve determinism and the number of observable events, allowing the generalization of results across different notions of opacity. Third, we propose three new algorithms for verifying language-based opacity, trace opacity, weak k-step opacity, weak infinite-step opacity, and strong k-step opacity that improve their respective algorithmic complexity.Opacity is a security property of discrete-event systems that asks whether, at any point of a computation, the secret is revealed to a passive intruder. The literature has introduced several notions of opacity, including language-based opacity, trace opacity, current-state opacity, weak k-step opacity, weak infinite-step opacity, strong k-step opacity, initial-state opacity, and initial-and-final-state opacity. In this work, we provide a complete and improved complexity picture of verifying the discussed opacity notions within the finite automata model. First, we focus on the complexity of deciding current-state opacity in systems with a restricted set of events and a restricted structure. Second, we present polynomial-time transformations among the notions that preserve determinism and the number of observable events, allowing the generalization of results across different notions of opacity. Third, we propose three new algorithms for verifying language-based opacity, trace opacity, weak k-step opacity, weak infinite-step opacity, and strong k-step opacity that improve their respective algorithmic complexity.