CODEWITHSUNDEEP
algorithmcomputer-sciencetime-complexity
oneCoderToRuleThemAll
oneCoderToRuleThemAll

Reputation: 865

Computing Algorithm Runtime?

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 !

Upvotes: 0

Views: 76

Answers (1)

Henry
Henry

Reputation: 43728

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

Upvotes: 2

Related Questions