# Resolve "(Learner1D) improve time complexity"

Closes #126 (closed) #104 (closed)

improves time complexity from O(N^2) to O(N log N) (for learning a function from 0 to N points).

Speed is now ~1000 points per second on my computer (given the default loss) and remains more or less constant untill 5000 points

obviously for small N (say 10 points) the old method was faster, for larger N (say >20, the new method is faster).

It does need to be said that according to my profiler, most of the time is spend on this line: be74ad62 (line 572)

please do verify that the results are noticeable for you as well.

Also do note that the complexity now is as follows:

Operation | Comblexity @ master | Complexity @ branch |
---|---|---|

tell(x,y) | O(N) | O(log N) |

ask(1) | O(N) | O(log N) |

loss() | O(N) | O(1) |

ask(k) | O(N*k) | O(k * log N) |

run 1..N | O(N^2) | O(N log N) |