# What is the difference between time complexity and sample complexity?

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.

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.