Page 130 [130]
OCR
4.2 HOW CAN THE PRESENTED METHODS BE IMPROVED... 129 — The worst case time complexity of the linear search algorithm is O(n). Why? (We do not encourage detailed discussion regarding big O notation.) — How many comparison operations does the binary search algorithm imply (for a list with n elements) in the “best case”? — How many comparison operations does the binary search algorithm imply (for a list with n elements) in the “worst case”? — The worst case time complexity of the binary search algorithm is O(log n). Why? [favourable moment for introducing the concept of binary tree] Another variant for students with less mathematical knowledge: — Given the numbers from 1 to 1,000, what is the minimum/maximum number of guesses needed to find a specific number if you are given the hint “guessed”/“missed” (linear search) or “guessed”/“higher”/“lower” (binary search) for each guess you make? The teacher might also guide students in discovering the reasons behind the superiority of binary search strategy against the linear one. A possible approach (that also promotes skill 2) is: the length of a list with n elements versus the height of a binary tree with n nodes. The following questions allow the teacher to introduce the concept of search space, too. In the essay entitled Thinking about computational thinking, the authors suggest methods for familiarizing grade 3 students with this concept (Lu & Fletcher, 2009). — How many elements of the search space are eliminated by each try (comparison operation) in the case of linear/binary search algorithm? (Another perspective: with each try, the current problem is reduced to searching in one shorter vs. half shorter list.) Since in the worst case binary search scenario the algorithm continues with the larger part of the divided sequence, the teacher can help students realize that starting with the middle element is an optimal choice (the larger part of the search space is minimal). After students have studied sorting algorithms too, it can be analysed when the “sorting + binary search” strategy is preferable instead of linear search. According to our experience, the above-presented approach has the potential to support students in realizing the relative value of the studied algorithms. 11.3.3 Exploring sorting strategies from an algorithm complexity perspective We suggest the following question sequence to be analysed: — How many comparison and swapping operations does the selection , bubble, insertion, and merge sort algorithm imply for the samples presented in the videos from figures 7.1, 7.2, 7.3, and 7.5? — What is the “best case”/“worst case” with respect to a sorting algorithm?
