Oldal 130 [130]
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 (com¬
parison 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 poten¬
tial 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 , bub¬
ble, 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?