Timeline for What is the Time Complexity of Linear Regression?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2021 at 8:19 | comment | added | offlinehacker | Indeed n and p are inverted, it confused me too. It would be nice if the author would fix the answer. | |
| Apr 15, 2020 at 15:17 | comment | added | Lucas Morin | from : math.stackexchange.com/questions/84495/…, you may have inverted the exponent on n and p. The complexity should be $np^2$, this is also in line with practical time complexity. | |
| Sep 4, 2018 at 8:09 | comment | added | RUser4512 | "why is the exponent of n, squared. if I have 3 weights then the error function computed over n training sets have to be recomputed for all the possible combinations of those 3 weights right." No. This would be true if you were doing a naive approach, but based on the closed formula for $\hat{\beta}$, you do not have to try every combination of weights | |
| Sep 3, 2018 at 18:01 | comment | added | user134132523 | why is the exponent of n, squared. if I have 3 weights then the error function computed over n training sets have to be recomputed for all the possible combinations of those 3 weights right. same goes for higher number of weights. that is why my reasoning was that the number of weights should be an exponent. and also in your calculation where is the limit on the number of possible iterations per weight? I am talking about a purely brute force approach even though its not the optimal way to go about it. | |
| Sep 3, 2018 at 15:23 | history | answered | RUser4512 | CC BY-SA 4.0 |