algorithm - Timecomplexity with given input and time -
what's easiest way time-complexity of function when input , time per input given?
for example:
n | 10 20 40 80 160 320 640 time | 1 3 9 60 475 3732 29835 how find time-complexity of table?
assuming, interested in polynomial complexities (o(n), o(n1.5), o(n2) ...).
the easiest way estimate time-complexity of function implementation @ last 2 largest datapoints.
you doubled (*2) input size n 320 640. , execution time increased factor of 8 (29835/3732 =7.994...).
thus, time complexity estimate o(n3) since 23=8. 1 should pay attention, estimate correct if tested on large enough datasets (n large) , lower-order terms not influence solution anymore. moreover, time-complexity of implementation of algorithm, not algorithm itself.
another useful technique understand complexities of code plotting them (t versus n) on log-log plot. since degree of polynomial determining complexity become slope of line on log-log plot, can give understanding of complexity , if reached asymptotic region or not. in addition, such plots can give idea of lower order terms, log-terms , etc.
however, usually, know supposed complexity of algorithm theoretical analysis, , may compare actual timings theoretical prediction. allows avoid lot of pitfalls during estimation process.
Comments
Post a Comment