A Common-Sense Guide to Data Structures and Algorithms

Ignoring Constants

But here’s the funny thing: in the world of Big O Notation, Selection Sort and Bubble Sort are described in exactly the same way.

Again, Big O Notation describes how many steps are required relative to the number of data elements. So it would seem at first glance that the number of steps in Selection Sort are roughly half of whatever N² is. It would therefore seem reasonable that we’d describe the efficiency of Selection Sort as being O(N² / 2). That is, for N data elements, there are N² / 2 steps. The following table bears this out:

N elements	N2 / 2	Max # of steps in Selection Sort
5	52 / 2 = 12.5	14
10	102 / 2 = 50	54
20	202 / 2 = 200	199
40	402 / 2 = 800	819
80	802 / 2 = 3200	3239

In reality, however, Selection Sort is described in Big ...