Java Illuminated, 5th Edition

15.1 Orders of Magnitude and Big-Oh Notation

Table 15.1 shows examples of various orders of magnitude for an algorithm as a function of the number of inputs n, along with the corresponding number of statement executions for different values of n.

TABLE 15.1 Comparisons of Various Functions Representing Running Times

Order of Magnitude	Number of Statements Executed
n = 10	n = 20	n = 1,000	n = 1 million
log n	2.23	3.23	Approx. 10	Approx. 20
n	10	20	1,000	106
n log n	22.3	64.6	Approx. 10,000	Approx. 20* 106
n2	100	400	106	1012
n3	1,000	8,000	109	1018
2n	1,024	Approx. 106	Approx. 10300	Approx. 10300000

Let’s look at an example to see how we can use these values. As we will demonstrate later in the chapter, Sequential ...