O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 N2 is. It would therefore seem reasonable that we’d describe the efficiency of Selection Sort as being O(N2 / 2). That is, for N data elements, there are N2 / 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required