Am I correct with these problems for Big-O, Big-Theta, Big-Omega or neither?

549 Views Asked by At

These are the problems:

  1. $x^{x^2}$ and $ 2^{2^x}$

  2. $\cos(x)$ and $\tan(x)$

  3. $x^3$ and $x$

My answers are:

  1. $x^{x^2}$ is O($ 2^{2^x} $)
  2. Neither Big O, nor Big Omega, nor Big Theta
  3. $x^3$ is Big-Omega($x$)

Are these correct answers?

1

There are 1 best solutions below

2
On BEST ANSWER

Here's a table, showing the general idea:

1.lim x^{x^2}/2^{2^x}
the limit is 0
because x^{x^2}/2^{2^x} = x^2 log x / 4^x => x^3/4^x so x^{x^2} is o(2^{2^x}) bucuase exponential functions grows faster than polynomials

2.lim cos(x)/tan(x) for this lim 1/sin(x) and lim sin(x) doesn't exist and we want x→∞ so this Periodic function doesn't have a big O notation .

3.for lim x^3/x we have infinity so x^3 is small omega (x) and () = (()) ⇒ () = Ω(), because Big Omega is used to indicate that ≥