# Proving n^2 = O(log n) [duplicate]

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?

• 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$. – Raphael Feb 17 '18 at 17:50
• How exactly? can you give a helping hand ? :) I'm having trouble figuring out proofs – crystyxn Feb 17 '18 at 17:52
• 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. – gnasher729 Feb 17 '18 at 19:09
• @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. – Raphael Feb 17 '18 at 19:31