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?

Quote:

---

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