Solutions to Lab 9 exercises & Reflection¶
Written solutions¶
The written solutions for this week can be download as PDF below.
Video explanations of some solutions¶
Videos for questions 2--4 and 6 are shown in the hints page.
If you want a refresher on what logarithms are then please watch this explanation:
Please let me know if you want clarification on any other exercises.
Reflection¶
Why do we use big-O notation instead of actual CPU time on actual machines?
In fact, if you were comparing a few different algorithms then it makes perfect sense to compare actual code implementations of the algorithms at hand. These time measurements would be very useful practically because they include real-world factors such as the CPU registers sizes, the cache sizes, etc.
So why do we still use big-O notation then?
Hints
This practical approach suffers from being "local", in the sense that it is very accurate for your local machines in space and time, and in the historical timeline.
Imagine you find a very good paper from 50 years ago but where the code was run on a machine from those days -- how useful would the time measurements shown there be to you nowadays?
The paper is also quite likely to have tested the algorithms on relatively small parameter sizes. Your machine is probably able to handle larger sizes, but this "practical paper" gives you little insight into what to expect.
This is why we prefer the use of big-O notation. The theoretical analysis of the algorithm should still apply 50 years on, as long as the general architecture of the machine is fairly similar.
The theoretical big-O analysis also identifies the important parameters affecting the complexity. It shows how these parameters affect the cost (polynomially or super-polynomially).
Info
You don't have to hand-in your reflection -- this is not an assessment. Keep your notes and go over them as you understand the material more. Some of the above ideas will become clear in one week, while others will be met again towards the end of the module!