Question

(a) Explain the difference between big-O and big-theta, and give examples of each to show the difference.
(b) How can we say that two functions have the same asymptotic complexity, using big-theta notation?
(c) Rank the following functions in order of increasing complexity (rate of growth), and indicate which functions have the same asymptotic complexity.
x²; x log(x); 2^x; log(x) + 7; 92x² + 57x + 3921; 4^x; 27x² + 8x³; 2^2x+5; log(x⁴²); 3x + 12.

Answer 1

a)

Big O always give the upper asymptotic bound, whereas big Theta always give the tight bound.

Everything that is Theta(f(n)) is also O(f(n)), but T(n) is said to be Theta(f(n)), if it is both O(f(n)) and Omega(f(n)).

Example, if f(n) = n, then theta(f(n)) = n.

Whereas Big-O of f(n) could be O(n), O(n²), O(n³), etc.

b) Two functions f1(n) and f2(n) have the same complexity if there exists positive constant integers c1, c2, c3, c4 such that for all n >= n0, we have

0 <= c1 * g(n) <= f1(n) <= c2 * g(n)

0 <= c3 * g(n) <= f2(n) <= c4 * g(n)

c)

The rank  in order of increasing complexity (rate of growth) is given as:

log(x) + 7, log(x⁴²), 3x + 12, x log(x), x²; 92x² + 57x + 3921; 27x² + 8x³; 2^x; 2^2x+5

log(x) and log(x⁴²) belong to the same asymptotic complexity.

x² and 92x² + 57x + 3921 belong to the same asymptotic complexity.

2^x and 2^2x+5 belong to the same asymptotic complexity.