On the complexity of the dual basis of a type I optimal normal basis

The complexity of the dual of a type I optimal normal basis of Fqn over Fq is computed to be either 3n−3 or 3n−2 according as q is even or odd, respectively. A partial converse of this result is also obtained.