0

On a recent test, I was asked whether the following is true or false:

True or False: $10n^3 = O \left( 0.42n^3 \right)$

Comparing the two functions as n approaches infinity, I get:

$ \lim_{n \to \infty} \frac{10n^3}{0.42n^3} = \frac{10}{0.42} \lim_{n \to \infty} \frac{n^3}{n^3} = \frac{10}{0.42} \lim_{n \to \infty} 1 = \frac{10}{0.42} $

$\frac{10}{0.42}$ is a positive constant, so $10n^3 = \theta \left( 0.42n^3 \right)$

I put false--and was marked wrong. Am I wrong? If so, can you show me how?

StudentsTea
  • 2,218
  • You have yourself provided a proof that it is true. – GFauxPas Jun 30 '16 at 23:29
  • False. $ 10n^3 $ and $ O(0.42n^3) $ are not the same thing. However, one is an element of the other. (I know equality is commonly abused with big-O notation, but I maintain that this is technically the correct answer to the question as stated) – cardboard_box Jul 01 '16 at 01:10
  • @cardboard_box - I see what you mean. What notation would you use? – StudentsTea Jul 01 '16 at 02:16
  • @StudentsTea if you're being taught that notation in a class, use it for that class. But I prefer the notation $ f(x) \in O(g(x)) $. There's a section about the notation on wikipedia. – cardboard_box Jul 01 '16 at 02:33
  • @cardboard_box I thought that might be it. I agree: theta, omega, and oh produce families of functions. It's amazing how there's also asymptotic behavior for how much rigor engineers and teachers are willing to put into their analysis though, isn't it. ;D – StudentsTea Jul 01 '16 at 02:38

2 Answers2

1

Multiplication by a constant doesn't affect big-O fit. All polynomials of degree 3 are of the same order, so $10n^3 = O(0.42 n^3)$ is true.

ConMan
  • 24,300
0

@ConMan led me to the answer; I'll write it here just a little more directly:

$g(n) = \theta (f(n))$ implies both $g(n) = \Omega (f(n))$ and $g(n) = O (f(n))$ are true.

So, if we can show $g(n) = \theta (f(n))$ is true (which we have done), then both both $g(n) = \Omega (f(n))$ and $g(n) = O (f(n))$ are also true.

StudentsTea
  • 2,218