In the correction of tutorial 3, you wrote that the computational complexity of grid search is O(W^DN). However, to me, if for each dimension (suppose there are D dimensions) we consider W different values, then for each data points (suppose we have N data points), we have to compute W^D times the loss. So in total, yes, we compute W^DN times the loss. But the loss itself if we consider the linear MSE is O(ND).
Thus, to me the total computational complexity of grid search with linear MSE is O(W^DNND). Where am I wrong?
Computational Complexity Grid Search
Hello,
In the correction of tutorial 3, you wrote that the computational complexity of grid search is O(W^DN). However, to me, if for each dimension (suppose there are D dimensions) we consider W different values, then for each data points (suppose we have N data points), we have to compute W^D times the loss. So in total, yes, we compute W^DN times the loss. But the loss itself if we consider the linear MSE is O(ND).
Thus, to me the total computational complexity of grid search with linear MSE is O(W^DNND). Where am I wrong?
N loss-computation-for-one-datapoint W^D
for linear models, loss-computation-for-one-datapoint is O(D)
only the D goes to the exponent, the N etc don't
Add comment