11.14 Big O Summary for This Chapter’s Searching and Sorting Algorithms¶

Searching and sorting algorithms covered in this chapter with the Big O for each

Algorithm	Location	Big O
Searching Algorithms:
Linear search	Section 11.7	O(n)
Binary search	Section 11.9	O(log n)
Recursive binary search	Exercise 11.18	O(log n)
Sorting Algorithms:
Selection sort	Section 11.11	O(n²)
Insertion sort	Section 11.12	O(n²)
Merge sort	Section 11.13	O(n log n)

11.14 Big O Summary for This Chapter’s Searching and Sorting Algorithms (cont.)¶

Big O values we’ve covered in this chapter along with a number of values for n to highlight the differences in the growth rates

n =	O(log n)	O(n)	O(n log n)	O(n²)
1	0	1	0	1
2	1	2	2	4
3	1	3	3	9
4	1	4	4	16
5	1	5	5	25
10	1	10	10	100
100	2	100	200	10,000
1000	3	1000	3000	10⁶
1,000,000	6	1,000,000	6,000,000	10¹²
1,000,000,000	9	1,000,000,000	9,000,000,000	10¹⁸

©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.

DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.