Welcome! Log In Create A New Profile


Big-O worked examples needed

Posted by crowne 
Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Big-O worked examples needed
March 31, 2008 09:56AM
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.
Re: Big-O worked examples needed
April 01, 2008 01:01PM
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.

The reverse calculation is similar.

I hope this helps.
Lazarus Aron
Sorry, only registered users may post in this forum.

Click here to login