Welcome! Log In Create A New Profile

Advanced

Review 2

Posted by aronl 
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
Review 2
September 10, 2008 09:36AM
Consider the table below and answer the question that follows .The table depicts the running time (seconds) dependant on input size (n) of three algorithms

Algorithm ____n = 100____n = 1000_____n = 10 000
___ A _________ 4 _________ 400 __________ 40 000
___ B _________ 9 _________ 90 ___________ 900
___ C _________ 21 ________ 31 ___________ 41

What is the running time complexity of algorithm A, B and C?
avatar Re: Review 2
September 10, 2008 04:47PM
Hi Lazarus.

Can you change this one. Was in assignment 1.

Thanks
Re: Review 2
September 12, 2008 09:47AM
Sorry!

Consider the table below and answer the question that follows .The table depicts the running time (seconds) dependant on input size (n) of three algorithms

Algorithm ____n = 4____n = 8_____n = 16
___ A _________ 16 _____ 256 ____ 65536
___ B _________ 17 ______ 65 _____ 257
___ C _________ 6 _______ 11 _____ 20

What is the running time complexity of algorithm A, B and C?
avatar Re: Review 2
September 12, 2008 10:51AM
I would say...

A O(2n)
B O(n2)
C O(n)

Is there a formula to use, or just plug away with growth rates?

Thanks
Re: Review 2
September 13, 2008 03:30PM
i suppose it's just by inspection really.
Re: Review 2
September 15, 2008 08:43AM
Answer given above is correct. There is no set formulae to use, the best way is by inspection.
Re: Review 2
October 16, 2008 01:47PM
This pattern may NOT be valid, but you're welcome to test it on more numbers.

With 0(n2), c/b = b/a (i.e. the third number divided by the second number is the same as the second number/first number)
Sorry, only registered users may post in this forum.

Click here to login