Computational complexity of $x x^H$

Question

Assume $x\in \mathbb{C}^{n\times n}$. What is the computational complexity (cost) of $x x^H$ where $H$ is the conjugate transpose?

I know this gives a symmetric matrix and we can divide by $2$ the number of operations involved. But I wonder if it can cost less than $O(n^2)$ (the cost of taking a direct product)?

Answer 1

The coefficients $x_i\overline{x_j}$ ($i<j$) of $xx^H$ are distinct for generic $x\in\mathbb{C}^n$, so you can't avoid needing $O(n^2)$ operations to get them.