Even programs that solve the same problem can differ greatly: depending on the algorithm chosen, one may finish instantly while another may not finish even after years. In the modern age of large-scale data, the concept of computational complexity determines the difference between a “program that works” and a “program that can be used.” In this lesson, you will learn how to express computational complexity using Big O notation and the efficiency of representative search and sorting algorithms.
Computational Complexity and Big O Notation
The efficiency of an algorithm is evaluated by “how quickly the amount of work increases as the number of data items n increases.” The notation used to express this is Big O notation. We ignore detailed coefficients and focus only on the “shape” of the increase.
・O(1): Constant, regardless of n. Example: Directly retrieving the i-th element of an array.
・O(log n): Even when n doubles, the amount of work increases by only one step. Example: Binary search.
・O(n): Proportional to n. Examples: Linear search and calculating a total.
・O(n log n): The standard for fast sorting. Examples: Merge sort and quicksort (on average).
・O(n²): Proportional to the square of n. When n becomes 10 times larger, the amount of work becomes 100 times larger. Examples: Bubble sort and selection sort.
Searching — The Difference Between O(n) and O(log n)
Linear search examines items in order from the beginning and requires up to n comparisons in the worst case (O(n)). Binary search compares the target with the middle of sorted data and narrows the range by half each time. Even in the worst case, it requires only about log2 n comparisons, or “the number of times n can be divided by 2 until it becomes 1” (O(log n)).
・Linear search: At most 1,000,000 comparisons.
・Binary search: Since 219＝524,288 ＜ 1,000,000 ≦ 220＝1,048,576, the item can be found with at most 20 comparisons.
The difference is 50,000 times. Even with 1 billion items, binary search requires only about 30 comparisons (230≒1.07 billion). This shows that the larger n becomes, the more decisive the choice of algorithm is. However, binary search requires the data to be sorted. That is why the next topic, “sorting,” is important.
Sorting Algorithms
Bubble sort is the simplest sorting method. It repeatedly compares two adjacent items and swaps them if they are in the wrong order. With n data items, it makes n−1 comparisons in the first pass, n−2 in the second pass, and so on. Therefore, the total number of comparisons is n(n−1)÷2, which is O(n²). When n＝10, this is 10×9÷2＝45 comparisons, but when n＝10,000, it rises to about 50 million comparisons. Selection sort (repeatedly selecting the smallest value from the remaining items and placing it at the front) is also O(n²).
In contrast, merge sort, which divides data into halves, sorts them, and merges them, and quicksort, which divides data into groups smaller and larger than a reference value, operate in O(n log n) time. When n＝1 million, n² is 1 trillion (1012), whereas n log2 n is about 20 million (106×20＝2×107). This is a difference of about 50,000 times, so O(n log n) algorithms are used for practical sorting.
Techniques for Algorithm Design
Ideas for writing efficient programs include ① divide-and-conquer (divide a problem into smaller parts, solve them, and combine the results; this is the idea behind merge sort and binary search), ② recording and reusing results that have already been calculated (to avoid repeating the same calculations), and ③ choosing appropriate data structures (if many searches are needed, prepare sorting or indexes in advance). A database “index” is also a mechanism that speeds up searches from O(n) to approximately O(log n), showing that all the topics learned in this course are connected.
- Big O notation describes “how the amount of work increases as n increases.” From fastest to slowest: O(1)→O(log n)→O(n)→O(n log n)→O(n²).
- Linear search is O(n), while binary search is O(log n) (and requires sorted data). Even with 1 million items, binary search takes at most 20 comparisons.
- Bubble sort and selection sort are O(n²) (n(n−1)÷2 comparisons). Merge sort and quicksort are O(n log n).
- When n is small, the difference is not significant, but as n grows, the choice of algorithm becomes decisive.
- Divide-and-conquer, reusing results, and improving data structures are standard techniques for speeding up programs.
Practice Problems
- Arrange the following computational complexities in order from fastest (slowest growth) to slowest: O(n²)、O(1)、O(n)、O(log n)
- When searching for a value by binary search in 10,000 sorted data items, what is the maximum number of comparisons required? Use 213＝8,192 and 214＝16,384 to answer.
- Find the number of comparisons needed to sort 100 data items using bubble sort. Then state approximately how many times the number of comparisons increases when the number of items becomes 1,000, or 10 times larger.
Answers and Explanations
- Answer: O(1) → O(log n) → O(n) → O(n²)
Explanation: O(1) is constant, O(log n) increases very slowly, O(n) is proportional, and O(n²) increases rapidly as a square. - Answer: At most 14 comparisons
Explanation: The range is halved with each comparison. 213＝8,192 is not enough for 10,000, while 214＝16,384 ≧ 10,000, so 14 comparisons are sufficient to narrow the range completely. This is dramatically fewer than the 10,000 comparisons required by linear search in the worst case. - Answer: For 100 items: 100×99÷2＝4,950 comparisons. For 1,000 items: 1000×999÷2＝499,500 comparisons, which is approximately 100 times as many (about 101 times).
Explanation: The number of comparisons is n(n−1)÷2, or O(n²). When the number of data items becomes 10 times larger, the amount of work becomes approximately 10²＝100 times larger. This is why O(n²) algorithms are unsuitable for large-scale data.