Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)
1. Comparison of keys
Keys 4 13 25 33 38 41 55 71 73 84 86 92 97
Index 0 1 2 3 4 5 6 7 8 9 10 11 12
We need to use binary search: worst case performance, because that will lead to the largest
possible number of key comparisons. In this list, we have 13 indices, because we need to start
counting the keys from k = 0. The formula we need to use is ⎡ log2(n + 1) ⎤.
⎡ log2(n + 1) ⎤ = log2 (13 + 1) = 3.80735492206 ≈ 4
Conclusion: when you look up a key with binary search, the largest possible number of key
comparisons in this list is 4.
2. Estimating performance
A.
Binary search
Average case of successful search: ~ log2 (n)
Average case of successful search in a sorted array of 100,000 elements:
~log2 (100,000) = 16.609640474436812 ≈ 16.6
Sequential/linear search
Average case of successful search: (n + 1) / 2
Average case of successful search in a sorted array of 100,000 elements:
(100,000 + 1) / 2 = 50000.5
As you can see the 1 in (n + 1) / 2 is neglectable, because it’s a really small number compared to
100,000. You will get: (100,000) / 2 = 50000.
An average successful search by binary search is .6 ≈ 3010 times faster than an
average successful search by sequential search.
B.
We have a sorted array of 100,000 elements. To draw a single graph for both
linear (= sequential) and binary search, we need to use the “Big O” notation. The big O notation is
used to classify algorithms. It is a function characterization according to rates of growth and it is
useful for analysing efficiency. In this case, we consider worst cases. The worst cases for the
binary and linear search algorithms are:
- Binary = O(log(n))
- Linear = O(n)
I drew a
single graph
in Python as
follows:
, Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)
This is the result I got, after I clicked “run”.
We can see that the number of operations (for 100,000 elements) with the binary search
algorithm, is a lot less than with linear search, if you consider worst case scenario’s. In this case, if
you want to find a key, it is better and way faster to use the binary search algorithm.
3. Binary search in flowchart
This in my flowchart for binary search, made in excel.
1. Comparison of keys
Keys 4 13 25 33 38 41 55 71 73 84 86 92 97
Index 0 1 2 3 4 5 6 7 8 9 10 11 12
We need to use binary search: worst case performance, because that will lead to the largest
possible number of key comparisons. In this list, we have 13 indices, because we need to start
counting the keys from k = 0. The formula we need to use is ⎡ log2(n + 1) ⎤.
⎡ log2(n + 1) ⎤ = log2 (13 + 1) = 3.80735492206 ≈ 4
Conclusion: when you look up a key with binary search, the largest possible number of key
comparisons in this list is 4.
2. Estimating performance
A.
Binary search
Average case of successful search: ~ log2 (n)
Average case of successful search in a sorted array of 100,000 elements:
~log2 (100,000) = 16.609640474436812 ≈ 16.6
Sequential/linear search
Average case of successful search: (n + 1) / 2
Average case of successful search in a sorted array of 100,000 elements:
(100,000 + 1) / 2 = 50000.5
As you can see the 1 in (n + 1) / 2 is neglectable, because it’s a really small number compared to
100,000. You will get: (100,000) / 2 = 50000.
An average successful search by binary search is .6 ≈ 3010 times faster than an
average successful search by sequential search.
B.
We have a sorted array of 100,000 elements. To draw a single graph for both
linear (= sequential) and binary search, we need to use the “Big O” notation. The big O notation is
used to classify algorithms. It is a function characterization according to rates of growth and it is
useful for analysing efficiency. In this case, we consider worst cases. The worst cases for the
binary and linear search algorithms are:
- Binary = O(log(n))
- Linear = O(n)
I drew a
single graph
in Python as
follows:
, Computational Thinking – Assignment 3 (Artificial Intelligence Year 1)
This is the result I got, after I clicked “run”.
We can see that the number of operations (for 100,000 elements) with the binary search
algorithm, is a lot less than with linear search, if you consider worst case scenario’s. In this case, if
you want to find a key, it is better and way faster to use the binary search algorithm.
3. Binary search in flowchart
This in my flowchart for binary search, made in excel.
