-
September 10th, 2009, 11:09 AM
#1
Runtime question
I have this problem:
Consider programs A and B that have been analyzed and found to have worst-case running times no greater than 2n2 and 100nlogn respectively.
in order to find out if A runs faster than B for certain values should i look for whichever runtime produces the smallest number?
ex: n = 1000
2n2 = 2000000
100nlogn = 30000 so program b runs faster. Is this the correct way to do this problem?
-
September 10th, 2009, 02:34 PM
#2
Re: Runtime question
Originally Posted by FeralDruidonWoW
in order to find out if A runs faster than B for certain values should i look for whichever runtime produces the smallest number?
In order to find out if A runs faster than B for certain values you should run A and B with those values as input and compare the runtime of each program.
Worst case merely implies that there exists some input x for which
A runs 2n^2 steps on, and there exists some input y for which B runs 100 n log n steps on, but it may very well be possible that for other inputs, A and B will have a much shorter run time.
Consider this program(pseudo-code):
Code:
DoSomething( integer array[n] )
integer sum <-- 0
If array[1] = 1 then
For i <-- 1 to n, do
sum <-- sum + array[i]
End For
End If
End
Clearly if array[0] is equal to anything but 1, the program runs in O(1) time, but it's worst case is about n steps (O(n) steps) - this will happen if array[1] is equal to 1.
Regards,
Zachm
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|