O(n²) : Java Glossary

It is a way of roughly comparing the speed of algorithms. Big O notation is a way of categorising how algorithms will perform as they are scaled up to handle more data. Most algorithms perform acceptably well when the number of items to process is small, but some become impossibly slow as the number of items increases.

If you invented a sorting algorithm that was o(n²) that means the sorting time is proportional to n² where n in the number of elements to sort. An o(n) sort would be one that has constant time per item, proportional to the number of items. An o(n²) algorithm might beat an o(n) algorithm for small n, but above some number, the o(n) will be faster.

Meaning of O(n) Notation
Notation	Meaning
O(1)	means constant. It does not depend on how many items there are, e.g. indexing an array.
O(n)	algorithm is linear. The time it will take is proportional to n. It takes the same amount of time to handle each item no matter how many items there are. RadixSort is O(n).
O(n log(n))	Most of the commonly used sorts.
O(n²)	An algorithm varies as the square of the number of times. If you have twice as many items to process it will take four times as long. Most novice sort have this unfortunate property.

There is a subtle difference between O(n²) and o(n²), Big-O vs Landau notation.

asymptotic notation
Big O Notation details
sort

	You can get the freshest copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/jgloss/onsquared.html	J:\mindprod\jgloss\onsquared.html
	Please email your feedback for publication, letters to the editor, errors, omissions, typos, formatting errors, ambiguities, unclear wording, broken/redirected link reports, suggestions to improve this page or comments to Roedy Green : . If you want your message, your name or email kept confidential, not considered for public posting, please explicitly specify that. Unless you state otherwise, I will treat your message as a letter to the editor that I may or may not publish in the feedback section. After that, it will be too late to retract it. If you disagree with something I said, please quote it and cite the web page where you found it, tell me why you think it is wrong, and, if possible, provide some supporting evidence. Threatening to kill me or spouting obscenities has yet to persuade me to change my mind.
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
view Blog	Your face IP:[38.107.179.214]
Feedback	You are visitor number 8,701.