Case
Computational Thinking Assignment 3
- Course
- Institution
Computational Thinking Assignment 3
[Show more]
Seller
Follow
TR19
Content preview
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller TR19. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.94. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67096 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now