Optimal upper bound on the number of states in the complement of an NFA
In the paper State Complexity of Concatenation and
Complementation of Regular Languages by Jirásek, Jirásková, and Szabari (LNCS Volume 3317, 2005, doi 10.1007/978-3-540-30500-2_17) very precise bounds for complexities for complement on non-deterministic automata are obtained. We do not need full details, but the authors cite an earlier report by one of them, stating:

Theorem 2. For any positive integer $n$, there exists a binary NFA $M$ of
$n$ states such that any NFA for the complement of the language $L(M)$ needs at
least $2^n$ states.

So it seems there is no better bound for complementation than via deterministic automata. At least in general.