what is the computational complexity of eigenvalue decomposition for a unitary matrix? is O(n^3) a correct answer?

In practice, $O(n^3)$. In theory, it has the same complexity of matrix multiplication and more or less all the "in practice $O(n^3)$" linear algebra problems, that is, $O(n^\omega)$ for some $2<\omega<2.376$. For this last assertion, see Demmel, Dimitriu, Holtz, "Fast linear algebra is stable". EDIT: this is in the usual numerical linear algerbra model where the basic operations (+,,*,/) are performed approximately in IEEE machine arithmetic and cost $O(1)$ each. If you consider multiple precision and variable complexities depending on the bit length of numbers, that is a completely different beast. 


Take a look at the following link (and references therein) for the complexity of various algorithms for common mathematical operations: Computational Complexity of Mathematical Operations. In particular, the complexity of the eigenvalue decomposition for a unitary matrix is, as it was mentioned before, the complexity of matrix multiplication which is $O(n^{2.376})$ using the Coppersmith and Winograd algorithm. 


I think the other answers are wrong. I periodically look up this problem and I believe it to be open. I will summarize my opinion:
As far as I can tell, nobody knows the computational complexity of the approximate eigenvalue problem. Edit: I stand corrected. Thanks Suvrit. 


Yep O(n^3) is right 

