Link between dimensionality of feature vectors and estimation I am wondering, how does the dimensionality of the feature space effect the estimation complexity?
Best
 A: This depends on the algorithm you choose.
The algorithms that suffer the most are deterministic ones that try to account for all different scenarios. In this case you would experience a phenomenon called combinatorial explosion, where the complexity rapidly increases with each new dimension added. Even if you have $d$ binary features, the number of possible combinations is $O(2^d)$, which can get out of hand quickly.
Luckily, Machine Learning algorithms are non-deterministic and don't have to account for all possible scenarios, but still in most cases they suffer computationally from more dimensions. I'll try to account how some popular ML algorithms are affected:


*

*One simple case you can think of are algorithms that make use of a distance measure like the Euclidean distance: 
$$
dist(x, y) = \sqrt{\sum_{i=1}^d{(x_i - y_i)^2}}
$$
whose computation time clearly increases linearly ($O(d)$) with the number of dimensions ($d$). Algorithms like k-Nearest Neighbors or k-means suffer from this.
Notes on kNN complexity
Notes on k-means complexity

*Another case involves algorithms that have to account for all of the features individually, for example Tree-based estimators (Decision Trees, Random Forests, etc.). These algorithms have to check each feature one-by-one to determine which one they will use for splitting the data. The computational time also increases linearly ($O(d)$) in this case. The criterion used for the split (Gini index, Information Gain, etc.) is irrelevant. Naive Bayes estimators, also befall under the same category.
Notes on tree complexity
Notes on NB complexity

*Finally, algorithms like neural networks, depend on their architecture. Regarding solely the computation time, single layer networks suffer the most from dimensionality (at most linearly), as they are affected essentially in one matrix multiplication. Deep networks, on the other hand, suffer much less because the number of dimensions effects only the first layer of the network. The designer of the network can choose the size of the subsequent layers as he wishes. In most cases it isn't even considered an important factor. That being said, more dimensions may cause the network to require more epochs to converge to a solution, but that can't be said for sure as it depends on the nature of the problem. If you're interested in learning more, I'd suggest reading the link below.
Study on NN complexity
