0

Could someone provide overhead of the following model for training (With respect to input size or if there are any relevant parameters). Overhead I mean somewhat like asymptotic time complexity form.

  1. Multiple linear regression models (Least Sqaures)
  2. Decision Tree (C 4.5 OR ID3)
  3. K nearest neighbor

Thank you.

samarasa
  • 1,287
  • 6
  • 18
  • 26
  • 3
    This question needs additional information and clarification. What are you attempting to *calculate* with these models? What forms will your data be given in? What are "C 4.5" and "K-nn"? Note that in statistics a "model" is a mathematical description of data; it is not an algorithm and therefore the concept of algorithmic complexity does not apply *per se*. – whuber Feb 14 '12 at 16:32
  • Thanks for your thoughts. I would like to know the time complexity of training in these models. – samarasa Feb 16 '12 at 04:23
  • 1
    Possible duplicate of [What algorithm is used in linear regression?](https://stats.stackexchange.com/questions/1829/what-algorithm-is-used-in-linear-regression) and https://stats.stackexchange.com/questions/282558/algorithmic-complexity-big-o-of-cart-tree-building and https://stats.stackexchange.com/questions/219655/k-nn-computational-complexity – Sycorax Jul 28 '18 at 15:57

1 Answers1

1

Linear regression

The complexity of linear regression depends on how you choose to solve the problem. This is a well-studied problem, and different methods are optimal in different contexts.

What algorithm is used in linear regression?

Decision Tree

Algorithmic complexity (big-O) of CART tree building

K-NN

k-NN computational complexity

Community
  • 1
Sycorax
  • 76,417
  • 20
  • 189
  • 313