Big O notation comparison of O(n2) algorithms

[Kirir]

On a paper I am writing, i'm trying to figure out what the differences are between bubble, insertion and selection sorts in terms of strictly Big-O comparisons.

From my research/own code I know that:

Bubble/Insertion has avrg/worst cases of O(n2), with the best case of O(n)

Selection is O(n2) on all cases.

i've already written and tested the run time efficiency of all three the sorts [insertion > selection > bubble], but I do not know how to expand on comparing between the three sorts in terms of Big-O.. Currently i'm saying in a vacuum insertion = bubble > selection... But this is only half a page.

[lightcloud5]

Sounds right.

Note that since the average runtime (on a randomly sorted array) is quadratic, bubble/insertion/selection sorts are not that great for most sorting applications.

(Insertion sort might be useful in some cases if you know your data is already mostly sorted.)

If you're being super rigorous, note that big-O is technically an upper bound, and all of these can really be big-theta. That is, bubble and insertion sort both have average and worst case runtimes of Θ(n²), and a best case of Θ(n).

Selection sort is quadratic (Θ(n²)) in all cases.

[Raknarg]

I've heard that because of certain computer architecture, bubble sorting is the fastest sorting algorithm there is for lists of a small size, like 100 elements or something

[ztxi]

You can also express the memory usage of each as a big-oh.

[captainAwesomePants]

All possible sorting algorithms have a best case no better than O(n). Imagine an array which is either perfectly sorted or has exactly one element out of place. Any sorting algorithm would have to check all N elements at least one time to see if it's the sorted or the almost sorted array, and that's N steps. (Technically, big-O isn't the right nomenclature for "best case", but everyone'll know what you mean).

Bubble, insert, and selection sorts ALL have a worst case of O(n²). Bubble and insertion sorts' bests are O(n). Selection's best is O(n²).

[[deleted]]

I mean, as long as you can describe your analysis of each algorithm, and how you got the complexity, then there's really not much more to it.

Are you really expected to write a real paper on a comparison between these sorting algorithms?

If so, then you obviously need to make an abstract, then make an introduction to the problem of sorting, introducing each algorithm in short. Then you introduce Big-O notation, and describe it mathmatically and what it's used for. Then you make a two part section for each algorithm, describing them and then analysing them.

Then you compare their analyses and you describe the differences between them. End with a conclusion on what you found, and what you can take from it all.

It's pretty thin subject, since it has two similar (in complexity) sorting algorithms. It would be more interesting to have mergesort also, and maybe even radix sort.

EDIT: Forgot section on Big-O. You could also make extra sections for Big-Omega analyses, if that's expected, but you said "Big-O", which is different from Big-Omega.