How is the complexity of PCA O(min(p^3,n^3))?

Covariance matrix computation is O(p²n); its eigen-value decomposition is O(p³). So, the complexity of PCA is O(p²n+p³).

O(min(p³,n³)) would imply that you could analyze a two-dimensional dataset of any size in fixed time, which is patently false.