0
$\begingroup$

This question already has an answer here:

This is how I would think it n^2 = O(log n)

f(n) <= c*g(n)

should c=1 ?

n0 = 1

n^2 <= log n

0 <= log n - n^2, for all n>=1

we take n=1 then 0 <= log(1) - 1^2

0 <= 0 - 1

0 <= -1

Therefore n^2 = O(logn) false?

Is this correct?

$\endgroup$

marked as duplicate by Raphael Feb 17 '18 at 17:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ No, this is false. As for your attempt, you don't get to set $n=1$; you need to show the inequality for all $n \geq n_0$. $\endgroup$ – Raphael Feb 17 '18 at 17:50
  • $\begingroup$ How exactly? can you give a helping hand ? :) I'm having trouble figuring out proofs $\endgroup$ – crystyxn Feb 17 '18 at 17:52
  • $\begingroup$ You have to show that no matter how large you choose c, and no matter how large you choose n_0, you will find n ≥ n_0 where n^2 > c log n. You might try to find an n such that n ≥ n_0, n > c, and n > log n. $\endgroup$ – gnasher729 Feb 17 '18 at 19:09
  • $\begingroup$ @crystyxn You need to look at the definition of O again -- it's all there. As for helping with the task at hand, you'll notice that a lengthy answer at the question I linked you was written by me. $\endgroup$ – Raphael Feb 17 '18 at 19:31

Browse other questions tagged or ask your own question.