(21/04/2012 05:52 PM)ProperBritish Wrote:  big O is just how many operations an algorithm does compared to the size of the data set.
bubble sort for example is O(n^2), i.e. for a data set of 40 it'll do ~160 operations.

I was reading shit randomly, and noticed that this is pretty much totally wrong.

O(n^2) means that increasing the data set by n times increases calculation time by n^2 times.  So if a data set of size X takes Y time, a dataset of n*X takes (n^2)*Y time.

Note that the big O notation only cares about the most significant term, so something like 3n^2+5n+8 will simply be O(n^2), not O(3n^2+5n+8) because that's a giant mess and because lower order terms doesn't matter that much when shit gets large.