Question

For each pair of functions f and g, write whether f is in O(g), Ω(g), or Θ(g). (latex format below)

       \begin{enumerate}
           \item $f = (n+1000)^4$, $g = n^4 - 3n^3$
           \item $f = \log_{1000} n$, $g = \log_2 n$
           \item $f = n^{1000}$, $g = n^2$
           \item $f = 2^n$, $g = n!$
           \item $f = n^n$, $g = n!$
       \end{enumerate}

Answer 1

The answer of the question is provided below, please comment if any doubts:

1.

f = (n+1000)^4

g = n^4 – 3n^3

Answer: f = Ω(g)

Proof:

• For “f = Ω(g)” there exists constants c and n0 such that they are positive and ,
  • 0 <= c*g(n) <= f(n) for all n>n0
• Here for all n>1, and for c=1, 0 <= n^4 – 3n^3 <= (n+1000)^4.
• Hence f = Ω(g).

2.

f = log₁₀₀₀ (n)

g = log₂ (n)

Answer: f = O(g)

Proof:

• For “f = O(g)” there exists constants c and n0 such that they are positive and ,
  • 0 <= f(n) <= c*g(n) for all n>n0
• Here for all n>1, and for c=1, 0 <= log₁₀₀₀ (n)<= log₂ (n).
• Hence f = O(g).

3.

f = n¹⁰⁰⁰

g = n²

Answer: f = Ω(g)

Proof:

• For “f = Ω(g)” there exists constants c and n0 such that they are positive and ,
  • 0 <= c*g(n) <= f(n) for all n>n0
• Here for all n>1, and for c=1, 0 <= n^2 <= (n^1000).
• Hence f = Ω(g).

4.

f = 2ⁿ

g = n!

Answer: f = O(g)

Proof:

• For “f = O(g)” there exists constants c and n0 such that they are positive and ,
  • 0 <= f(n) <= c*g(n) for all n>n0
• Here for all n>3, and for c=1, 0 <= 2ⁿ<= .n!
• Hence f = O(g).

5.

f = nⁿ

g = n!

Answer: f = Ω(g)

Proof:

• For “f = Ω(g)” there exists constants c and n0 such that they are positive and ,
  • 0 <= c*g(n) <= f(n) for all n>n0
• Here for all n>1, and for c=1, 0 <= n! <= nⁿ
• Hence f = Ω(g).