# solutions to big oh questions in exam papers

Posted by aronl
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 solutions to big oh questions in exam papers October 04, 2006 08:56AM IP/Host: ---.unisa.ac.za Registered: 13 years ago Posts: 88 Rating: 0
Hi here are some solutions for the 2004/2005 big oh questions

2004 question 1b)

algorithm A - O(n) as n increases by 10 the running time also increases by 10.

algorithm B - O(n2) (that's n squared) as n increases by 10 the running time increases by 10 squared (ie 100).

algorithm C - O(log n)(thats log to the base 10) the running time increases slowly. Running time T = 10 log n - 10.

When you see that the running time is increasing slowly it is most likely a log function.

2005 question 1a)

Algorithm A O(n) see A above

Algorithm B O(n log n) (thats log to the base 10) Running time T = 2n log n.

If you look at this algorithm you will notice that it is not quite O(n) nor is O(n squared). It is someting in between hence it most likey O(n log n). From this you can determine that T=2n log n.

regards
Lazarus
 Re: solutions to big oh questions in exam papers October 04, 2006 10:08AM IP/Host: ---.cache.isnet.net Registered: 13 years ago Posts: 133 Rating: 0
I spent a good hour on the 2004 Big O questions and I wasnt quite sure of my answers. Turns out I had algorithm B completely wrong, thanks for helping out!
 Re: solutions to big oh questions in exam papers October 05, 2006 11:43PM IP/Host: ---.3g.vodacom.co.za Registered: 13 years ago Posts: 240 Rating: 0
Hi,

I have recently moved and have not received any post from UNISA lately. Can anyone please send me exam papers to esckays@gmail.com

Did we receive any answer to the exam papers ? If not, does anyone have any suggested solutions.

Thanks,
Esckays
 Re: solutions to big oh questions in exam papers October 08, 2006 03:20PM IP/Host: ---.saix.net Registered: 13 years ago Posts: 7 Rating: 0
Hi there

Any one knows the solution to Algo C in the 2005 paper?

 Re: solutions to big oh questions in exam papers October 08, 2006 03:26PM IP/Host: ---.saix.net Registered: 13 years ago Posts: 470 Rating: 0

algorithm A
When n=100 2ms per n
When n=1000 2ms per n
When n=10000 2ms per n
so O=(n)

algorithm B
n=100 4ms per n
n=1000 6ms per n
n=10000 8ms per n
time grows more than n but less than n2 (square)
so O=(n*log2n)

algorithm C
always takes 54ms so O=(1) {it never changes regardless of the size of n}

b) i) O=(n2) (square)
b) ii) O=(n) {n+n}
 Re: solutions to big oh questions in exam papers October 08, 2006 03:32PM IP/Host: ---.saix.net Registered: 13 years ago Posts: 7 Rating: 0
Ok great! That makes sense!!

Thank you & good luck for 2morrow...
 Re: solutions to big oh questions in exam papers October 08, 2006 03:46PM IP/Host: ---.88.28.196.gin.co.za Registered: 13 years ago Posts: 133 Rating: 0
for algorithm B, O=2nlogn.
for n=1000 := 2*1000*3 = 6000
for n=10000:= 2*10000*4 = 80000
 Re: solutions to big oh questions in exam papers October 08, 2006 06:56PM IP/Host: ---.3g.vodacom.co.za Registered: 13 years ago Posts: 240 Rating: 0
for algorithm B, O=2nlogn.
for n=1000 := 2*1000*3 = 6000
for n=10000:= 2*10000*4 = 80000

Yes, but Big-O will still be nlogn. Constants can be ignored, so O(n*logn) is my bet.
Sorry, only registered users may post in this forum.