Let $U\in \mathbb{R}^{d\times d}$ be an orthogonal matrix, i.e., $U^T=U^{-1}$.
Any orthogonal matrix can be written as a product of ${n \choose 2 }= \frac{n(n-1)}{2}$ Givens rotations, i.e., $U=R_1\cdots R_{n(n-1)/2}$.
However, some orthogonal matrices might be represented with fewer Givens rotations. Is it possible to compute the smallest number of Givens rotations needed to represent an orthogonal matrix? Furthermore, if we know a given orthogonal matrix can be represented with few Givens rotations, is it known whether one can the usual $O(d^3)$ time of matrix decomposition algorithms like QR decomposition?