Nupic Algorithms complexity

What are the time complexities for the Nupic algorithms like Spatial Pooler and Temporal Pooler?

1 Like

Can you be more specific with your question? “Time complexities” can mean so many things.

1 Like

All of our algorithm implementations are “fixed resources” in that there is a hard upper bound on the memory usage and time-per-record. So the algorithms are O(n) where n is the number of records. However, it may appear otherwise initially because the network has not become fully saturated. I.e. there may be a maximum number of segments per cell but only a subset of those have been allocated so far. A good way to know how long a given network will take to process a record after being fully trained is to feed in data, plot the time-per-record over time, and estimate the asymptotic upper bound.

I can’t give specific times, even for a specific algorithm, since they are highly dependent on the number of columns, cells per column and segments per cell for Temporal Memory, and potential pool size for Spatial Pooling. But regardless of the parameters, the time-per-record will converge to some constant value when the algorithm has hit the upper bounds.

Here are the results from my implementation and you can see the convergence as @scott described.
Distal = Temporal Memory
Proximal = Spatial Pooler

1 Like