Show that $0.01n \log n - 2000n+6 = O(n \log n)$.

Starting from the definition: $O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(n), \forall n\geq n_0 \}$

For $f(n) = 0.01n \log n - 2000n+6$ and $g(n) = n \log n$

Let $c = 0.01\implies 0.01n \log n - 2000n + 6 \leq 0.01 n \log n$

Subtract $0.01 n \log n$ from both sides: $$-2000n +6 \leq 0$$ Add $2000n$ on both sides: $$2000n \geq 6$$ Divide by $2000$: $$n\geq 6/2000$$

If $n \in \mathbb{N}^*\implies n \geq 0\implies n_0 = 0$


$$0.01n \log n - 2000n+6 = O(n \log n)$$

I'm not sure if what I did is completely correct and if $n_0 = 0$ is actually a good answer.. If it's correct, can it be done another easier way? and if it's not correct, where did I go wrong?

  • $\begingroup$ In the step after where you write "let $c=0.01$" you assume that $0.01n\log n - 2000n + 6\leq 0.01n\log n$. This is not a valid proof because you're essentially assuming what you want to prove. $\endgroup$ – Tom van der Zanden Nov 9 '19 at 9:36
  • 1
    $\begingroup$ Isn't that the point? To pick a $c$ that is convenient? $\endgroup$ – C. Cristi Nov 9 '19 at 9:48
  • $\begingroup$ Yes, you can pick any $c$ that you like. However, writing "$c = 0.01\implies 0.01n \log n - 2000n + 6 \leq 0.01 n \log n$" is not valid reasoning because we have no way of knowing that what comes after "$\implies$" is true. You're assuming what you want to prove. $\endgroup$ – Tom van der Zanden Nov 9 '19 at 9:54
  • $\begingroup$ @TomvanderZanden then what should I do? $\endgroup$ – C. Cristi Nov 9 '19 at 10:09
  • $\begingroup$ Essentially write down your proof in the reverse order. Start by assuming that $c=0.01$ and $n\geq 6/2000$, then derive that $0.01n \log n - 2000n + 6\leq 0.01\log n$. $\endgroup$ – Tom van der Zanden Nov 9 '19 at 10:39

Definition of big-O with c = 0.01 and n0 = 1. For a proof of big-theta you’d show the limit of f(n) / (n log n) exists and is > 0.

If you had the function f(n) = 0.01 n log n + 2000n + 6, where c = 0.01 doesn't work, a nice large c = 2019 will make the O(n) proof very easy.

| cite | improve this answer | |

Here's a different way of proving that $0.01 \log n - 2000n + 6$ is $O(n \log n)$.

If $f$ and $g$ are monotonically increasing functions and there exists some $x_0$ such that $g(x_0) > 0$, then $f \in O(g)$ if and only if $\exists a, b \colon \forall x \colon f(x) \leq ag(x) + b$. (Proof left as an exercise to those readers who feel up to the challenge. It's not hard, and it also works for continuous functions if you demand something slightly more general from $g$.)

However, the $-2000n$ term makes your functions not satisfy this requirement. However, we can rewrite:

$$0.01n \log n − 2000n + 6 = n(0.01 \log n - 2000) + 6$$

When $n$ is large enough you'll have $0.01 \log n - 2000 > 1$, and from that point onwards $f$ is monotonically increasing. In particular:

$$0.01 \log n - 2000 > 1 \Leftarrow 0.01 \log n > 2001 \Leftarrow \log n > 200100$$

Which holds when $n = 2^{\log n} > 2^{200100}$, assuming $2$ is the base of your logarithm.

Apply the theorem at the top of my post with $a = 1$ and $b = 6$, except $N$ has to be at least $2^{200100}$, and argue that the restriction to $n > 2^{200100}$ doesn't invalidate the conclusion of the theorem.

Alternatively, observe that both functions are continuous and that $n \log n$ satisfies the extra property which I left as an exercise for the reader. Then the theorem applies directly.

Of course, if your problem is homework and your teacher hasn't proven the theorem to you, you should probably prove it yourself.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.