Welcome! Log In Create A New Profile

# Review 2

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
 Review 2 September 10, 2008 09:36AM Registered: 14 years ago Posts: 88 Rating: 0
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?
 Re: Review 2 September 10, 2008 04:47PM Registered: 11 years ago Posts: 423 Rating: 0
Hi Lazarus.

Can you change this one. Was in assignment 1.

Thanks
 Re: Review 2 September 12, 2008 09:47AM Registered: 14 years ago Posts: 88 Rating: 0
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?
 Re: Review 2 September 12, 2008 10:51AM Registered: 11 years ago Posts: 423 Rating: 0
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 Registered: 11 years ago Posts: 79 Rating: 0
i suppose it's just by inspection really.
 Re: Review 2 September 15, 2008 08:43AM Registered: 14 years ago Posts: 88 Rating: 0
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 Registered: 12 years ago Posts: 387 Rating: 0
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