Big O Notation

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

0
  Related Posts