[threeducks]

Without looking at the code, O(N * k) with N = 9000 points and k = 50 dimensions should take in the order of milliseconds, not seconds. Did you profile your code to see whether there is perhaps something that takes an unexpected amount of time?

[romanfll]

The '2 seconds' figure comes from the end-to-end time on a standard laptop. I quoted 2s to set realistic expectations for the user experience, not the CPU cycle count. You are right that the core linear algebra (Ax=b) is milliseconds. The bottleneck is the DOM/rendering overhead, but strictly speaking, the math itself is blazing fast.

[moralestapia]

This is great Roman, congrats on the amazing work :)!

[donkeybeer]

If he wrote the for loop in python instead of numpy or C or whatever it could be a plausible runtime.

[jdhwosnhw]

Thats not how big-O notation works. You don’t know what proportionality constants are being hidden by the notation so you cant make any assertions about absolute runtimes

[threeducks]

It is true that big-O notation does not necessarily tell you anything about the actual runtime, but if the hidden constant appears suspiciously large, one should double-check whether something else is going on.

[yorwba]

Each of the N data points is processed through several expensive linear algebra operations. O(N * k) just expresses that if you double N, the runtime also at most doubles. It doesn't mean it has to be fast in an absolute sense for any particular value of N and k.

[akoboldfrying]

Didn't read TFA, but it's hard to think of a linear algebra operation that is both that slow and takes time independent of n and k.