BIG O proof

**taurus** · April 5th 2010, 10:54 PM

How do I prove the following:
O(n^2 logn) is also O(n^3)?

**CaptainBlack** · April 5th 2010, 11:23 PM

Originally Posted by taurus

How do I prove the following:
O(n^2 logn) is also O(n^3)?

$f(n)\in O(n^2 \log(n))$

means there exists a constant $k>0$ and an $N>0$ such that for all $n>N$ :

$|f(n)|<k n^2 \log(n)$

Now for $n>0$ we have $n>\log(n)$ so for $n>N>0$ :

$|f(n)|<k n^3$

etc.

CB

**taurus** · April 7th 2010, 01:38 AM

You will have to expand on that, I have no clue how to go on...

**CaptainBlack** · April 7th 2010, 02:35 AM

Originally Posted by CaptainBlack

$f(n)\in O(n^2 \log(n))$

means there exists a constant $k>0$ and an $N>0$ such that for all $n>N$ :

$|f(n)|<k n^2 \log(n)$

Now for $n>0$ we have $n>\log(n)$ so for $n>N>0$ :

$|f(n)|<k n^3$

etc.

CB

Originally Posted by taurus

You will have to expand on that, I have no clue how to go on...

So there exists a constant $k>0$ and an $N>0$ such that for all $n>N$ :

$|f(n)|<k n^3$

hence $f(n)\in O(n^3)$

CB

Thread: BIG O proof

LinkBack

Thread Tools

Display

BIG O proof

Similar Math Help Forum Discussions

delta-epsilon proof, but it's not the proof that's stumped me!

Proof theory: example of an existence proof of a proof?

Convert the following equational proof into a Hilbert Proof

Proof with algebra, and proof by induction (problems)

proof that the proof that .999_ = 1 is not a proof (version)

Search Tags