This is more of a CS question, but hopefully someone can help me. If a particular algorithm has a runtime of T(100) = 20, how can I estimate the runtime of T(400) given, a) T(n) = O(n) or b) T(n) = O(n^2) ? For a, I figured that if 100 elements took 20 units(of space or time), then linearly 400 elements would take around 80 units. Is this kind of thinking correct ? If so, how can approach b) ? If not, what is the correct way to compute this ? Thanks !
1
-
Well, O(n) denotes asymptotic bounds... so that means that approaching it from 100 to 400 will, most probably, not be accurate at all. However, with only that data, I guess there is not too much you can do.Javi– Javi2014-10-05 06:32:16 +00:00Commented Oct 5, 2014 at 6:32
Add a comment
|
1 Answer
Making a few assumptions like n is big enough that you really see the asymptotic behaviour and the algorithms are Omega(n) and Omega(n^2) respectively you would proceed like this:
a) T(n) = c * n; given that T(100) = 20 we find c = 0.2 and T(400) = 80
b) T(n) = c * n^2; T(100) = 20 -> c = 0.002; T(400) = 320
