I'm curious if there are any analytical or empirical methods to estimate the time it would take to process a data set (grouping or various prediction algorithms). Known variables would obviously include the size of the dataset, but also the types of variables (continuous/discrete), the number of factors for discrete variables, the amount of memory available, and processor power.

This sounds like a long shot to me, but I thought I'd throw it out there anyways.


The short answer is yes. You can use asymptotic analysis to determine how the algorithm's runtime scales as the size of all important variables goes to infinity. For most conventional algorithms this runtime is known (typically written O(...) where (...) is a function of the important variables). For many applications and datasets, this is sufficient to get a ballpark estimate of the run time (i.e. plug your values into the function, which gives you the number of steps required; divide by the speed of your processor in cycles/second; maybe multiply by one hundred as an upper bound guess at the constant factor)

If you need a tighter estimate, you can then run the algorithm for several smallish sample inputs, and use the average times on these small inputs to get a better estimate of the lower order terms and constants in the asymptotic runtime. Alternatively, you can find the paper where the algorithm was first introduced or analyzed (or find a good textbook written from a Computer Science prospective). Often this will furnish you with a more precise estimate.

| cite | improve this answer | |

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.