# Does curse of dimensionality also affect principal component analysis calculations?

Based on this post, the Big-O notation for the complexity of calculating principal components analysis is $$O(p^2n+p^3)$$ for a dataset of size $$n$$ with $$p$$ features.

I understand that PCA is often performed for dimension reduction purposes, however given the seemingly high cost in computational resources for performing PCA, wouldn't the PCA itself be too expensive to calculate in many cases?

For example if I can't fit a given linear regression or machine learning model to a large training dataset because there are far too many features, wouldn't there be too many features to perform a PCA as well?

• "Big O ... isn't a good tool to actually compare running times of different methods". I'm not sure I agree with that. As you point out, it's not the end-all, i.e., there can be very real cases where an $O(n)$ process runs slower than $O(n^2)$ for most reasonable values of $n$...but that's usually the exception, not the rule. I think the correct answer starts in your first paragraph; curse of dimensionality typical refers to overfitting, not runtime costs. Low-Rank PCA is a method used to mitigate the curse of dimensionality. – Cliff AB Jan 28 at 20:56
• Thanks, this makes more sense. I see there are more efficient ways to do the matrix calculations in PCA, or limit PCA to top $k$ eigenvectors (see this post stats.stackexchange.com/questions/268935/…). – RobertF Jan 28 at 21:00