Question

Suppose that Algorithm A has runtime complexity O(n3) and Algorithm B has runtime complexity O(n logn), where both algorithms solve the same problem. (a) How do the algorithms compare when n = 12? (b) How do the algorithms compare when n is very large?

Answer 1

a)

for n = 12

A takes O(12^3) = 1728

B takes O(12log12) = 43

So, B is more efficient than A

b)

for very larger n, nlogn is always more efficient than n^3, so B is always faster than A