There is a thread on the my.unisa discussion forum, which discusses difficulty experienced when trying to do the Big-O exercises.
I agree, and I would like to see some worked examples, specifically covering O(log(n)) and O(n log(n)).
Also the assignment questions give a base running time of 10 s for input size 100, does this mean that we need to work out the input number for 1 s and then apply that to calculate the running time for input size 1000.
Finally the reverse calculation where we are given 80 s running time and need to calculate the input size for a function with cubic growth, is a bit tricky.
Luckily this is multiple choice because I can kind of work it out and then choose the option which most closely matches by calculations, however this approach to math is frustrating. I would really like to see some more worked examples, and an explanation of the method of calculation.
Tutorial Letter 102 provides a comprehensive example of this type of question.
Consider the example given on page 6 of tutorial letter 102.
If an algorithm takes 1 second to run with a problem size of 8, what is the time requirement (approximately) for that same algorithm with a problem size of 16?
Lets look at the O(n 2) problem [n squared problem].
This means that an input of n=8 will result in our basic operation being run approximately n*n = 64 times in our algorithm. These 64 operations takes 1 second to run. Now a problem size of 16 will result in 16*16 = 256 operations.The question is how long will 256 operations take. The calculation and answer in given in Tutorial letter 102.