What is the the difference between time complexity and sample complexity in the context of algorithm development?

I'm currently studying the sparse Fourier transform and this idea of sample complexity keeps coming up. The majority of sample complexity literature is in the context of machine learning which is not what I'm interested in.


Some of those notions can seem quite vague, and may even depend on the field.

In algorithmics, different types of complexities come at play. One could be related to actual implementations (machine or computational complexity). Another to data access (sample, training set complexity).

Computational complexity is generally machine-, transmission-, power dependent. You have for instance time-complexity (the time need to run) or space-complexity (the memory required).

Data complexity are generally less machine dependent, and more conceptual. Sample complexity can be an estimate of the number of operations required, depending on the number of samples. In the Landau notation, an $O(N^3)$ algorithm grows as the cube of the number of samples $N$. It is a gross measure of scalabilty. Here, one is not concerned with data precision, storage, etc. If one can bound the execution time of operations, one could relate sample complexity to time complexity, but complicated computer architectures make this conversion doubtful: caching, pipelining, parallelizing, swapping alter a lot the expectations. In learning tasks, "data complexity" may refer to the quantity of data to be learned, on the training sets, to achieve certain prediction goals. One classical measure is the Kolmogorov complexity.

A related SE question: Computational complexity vs other complexities.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.