Skip to main content
IBM 
ShopSupportDownloads
IBM HomeProductsConsultingIndustriesNewsAbout IBM
IBM : developerWorks : Java : Education - online courses
Java Collections Framework
Download tutorial zip fileView letter-sized PDF fileView A4-sized PDF fileE-mail this tutorial to a friend
Main menuSection menuGive feedback on this tutorialPrevious
Next Section
6. Algorithm support
  


Big-O notation page 6 of 6


Performance of sorting and searching operations with collections of size n is measured using Big-O notation. The notation describes the complexity of the algorithm in relation to the maximum time in which an algorithm operates, for large values of n. For instance, if you iterate through an entire collection to find an element, the Big-O notation is referred to as O(n), meaning that as n increases, time to find an element in a collection of size n increases linearly. This demonstrates that Big-O notation assumes worst case performance. It is always possible that performance is quicker.

The following table shows the Big-O values for different operations, with 65,536 as the value for n. In addition, the operation count shows that if you are going to perform multiple search operations on a collection, it is faster to do a quick sort on the collection, prior to searching, versus doing a linear search each time. (And, one should avoid bubble sorting, unless n is really small!)

DescriptionBig-O# OperationsExample
ConstantO(1)1Hash table lookup (ideal)
LogarithmicO(log base 2 of n)16Binary search on sorted collection
LinearO(n)65,536Linear search
Linear-logarithmicO(n x log base 2 of n)1,048,576Quick sort
QuadraticO(n x n)4,294,967,296Bubble sort

Legend: n = 65536


Next Section
Main menuSection menuGive feedback on this tutorialPrevious
PrivacyLegalContact