Wednesday, August 10, 2011

Big O Notation - Order these functions in order based on an increasing running time?

Mathematicians came up with the Big-O notation to group functions whose results increased at a similar rate to one another. So if you have one function count the numbers from 1 to n, it will count them linearly or O(n). If you have another count the odd numbers from 1 to n, you have O(1/2 X n) = 1/2 O(n). But they decided that all Big-O notations in the form kO(n), where k is a constant number, should be just called O(n). The same goes for O(2n^2) = 2O(n^2) = O(n^2). So O(3n^2) = 3O(n^2) = O(n^2). They group them together because if you compare the speeds that an O(2n) program vs. O(3n) program runs, they are virtually identical, even if n becomes a really large number. BUT, if you compare either of these to the speed that a program that runs in O(n^2) runs, you find that as n gets really large, the O(n^2) program is still running a long time after the O(n) programs are finished. You can also determine the minimum amount of time that each function will take to run its course. That is what they call the Little-O notation. So they are used just to generalize the upper and lower limits for functions or programs. Don't think of the Big-O and Little-O notation to mean anything other than that.

No comments:

Post a Comment