Asymptotic notation

• TC(n) = 4. n2 + 10 . n

• TD(n) = 6 . n2

• For large n, Alg C is superior to Alg D

• I.e.

? no: ? n ? no : TD(n) ? TC(n)

• But...

? n : TD(n) ? [6/4] . TC(n)

• i.e., even for large n, Alg D is “worse” by at most a constant factor

Previous slide

Next slide

Back to first slide

View graphic version