DEV Community

loading...

Discussion on: Insertion Sort with Javascript

Collapse
yuripredborskiy profile image
Yuri Predborskiy

Thanks, nice article! But if you want to apply time complexity outside of academia (like, real world scenario), I recommend dropping constants and keeping only the biggest power of n (feel free to correct my spelling, I'm not strong in academic / math English). In this case (insertion sort) it would simply be n2.

Collapse
supunkavinda profile image
Supun Kavinda Author

You are correct, in general it is called order of growth.

Order of growth is used to simplify the process of analyzing, which converts an(2) + bn + c to n<sup>2</sup> for our ease. So, for the worst case of insertion sort the time complexity (running time) can be simplified to n2 (notated as Θn2)

What we do is, assume the lower-order terms are relatively insignificant for large values of n. And, we drop the constants too for the same reason. It is all for making the analyzing process easy for ourselves.

For small inputs, the running time may depend on lower-order terms and constants. But, when the number of inputs increase, it almost depend on the leading term.

Thanks!

Collapse
yuripredborskiy profile image
Yuri Predborskiy

Great explanation, thanks!