What is “Big O” Notation?
Big O notation: Indicates the worse-case run time for an algorithm–that is, how hard an algorithm may have to work to solve a problem.
Big O example:
Suppose an algorithm is designed to test whether the first element of an array is equal to the second. If the array has 10 elements, this algorithm requries one comparison. If the array has 15,000 elements, it still requires one comparison. In fact, the algorithm is completely independent of the number of elements in the array. This algorithm is said to have a constant run time, which is representing in Big O notation as O(1). An algorithm that is O(1) doesn not necessarily require only one comparison. O(1) just means that the number of comparisons is constant–it does not grow as the size of the array increases. An algorithm that tests whether the first element of an array is equal to any of the next three elements is still O(1) even though it requires three comparisons.
Reference: Deitel, P.(2009) Java how to program: Late objects version, 8th Edition. Uppper Saddle River: Prentice Hall.
Big O Notation – Useful Links
NIST Information Technology Labratory
NIST Information Technology Labratory – Software and Systems Division
NIST Dictionary of Algorithms and Data Structures
National Institute of Standards and Technology – big-O Notation
National Institute of Standards and Technology – little-O Notation
Wolfram Mathworld – Landau Symbols