Case uitwerking
Computational Thinking Assignment 3
- Instelling
- Vrije Universiteit Amsterdam (VU)
Computational Thinking Assignment 3
[Meer zien]Voorbeeld 2 van de 8 pagina's
Voorbeeld 2 van de 8 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
Volgen
Voorbeeld van de inhoud
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.
Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:
Bewezen kwaliteit door reviews
Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!
In een paar klikken geregeld
Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.
Direct to-the-point
Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper TR19. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 64419 samenvattingen verkocht
Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen
Laatst bekeken door jou
College aantekeningen ·
Chapter 5 Marketing year 1 BE course
Samenvatting ·
Samenvatting boek Medische Kennis H2-H15, examenstof opleiding doktersassistente (kerntaak 1).
Tentamen (uitwerkingen) ·
Test Bank for M: Marketing, 8th Edition by Dhruv Grewal
Voordeelbundel ·
Semester 2, Modetechnologie 1ste jaar
