# 2004 exam paper - question 1

Posted by esckay
Announcements Last Post
myUnisa availability 21 to 24 March 2019 03/25/2019 12:25PM
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
 2004 exam paper - question 1 October 08, 2006 09:47PM IP/Host: ---.3g.vodacom.co.za Registered: 13 years ago Posts: 240 Rating: 0
can anybody help with question 1a of the 2004 exam paper....

what I get is the following .... (but i dont think its right)

The following six expressions represent the running times of various algorithms in terms of the input size N:

N/1000 + 23
1000/N + 23
3 log 3 N
log N2
N2 - 23N
1023

1023, 1000/N + 23, 3 log 3 N, N/1000 + 23, log N2, N2 - 23N

It this right ?
 Re: 2004 exam paper - question 1 October 09, 2006 12:15AM IP/Host: ---.88.28.196.gin.co.za Registered: 13 years ago Posts: 133 Rating: 0
From another post:

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: 2004 exam paper - question 1 October 09, 2006 08:37AM IP/Host: ---.3g.vodacom.co.za Registered: 13 years ago Posts: 240 Rating: 0
Hi,

I saw that post, but that only answers Q1B of the 2004 paper, not Q1A of the 2004 paper.

Exam 2004 Question 1 A:
The following six expressions represent the running times of various algorithms in terms of the input size N:

N/1000 + 23
1000/N + 23
3 log 3 N
log N2
N2 - 23N
1023