Big O Notation - Prove ( n l o g n ) 2 − 4...

Joshua Foley

Joshua Foley

Answered

2022-07-03

Big O Notation - Prove ( n l o g n ) 2 4   is   O ( n 4 ).
My Attempt:
C ( n 4 ) ( n l o g n ) 2 4
i assumed n > 0, so that n > log ( n )
( n ) 2 > ( log n ) 2
n 2 > log 2 ( n )
n 4 > n 2 log 2 ( n )

Answer & Explanation

pampatsha

pampatsha

Expert

2022-07-04Added 15 answers

Explanation:
This is a sketch prove, it's not fully complete, but it should give you a hint:
Consider the function f ( x ) = x log ( x ) f ( x ) = x 1 x , which is strictly positive for x > 1, as such, f(x) this function is strictly increasing on ( 1 , + ) x > log ( x ) x 2 > x log ( x ) x 4 > ( x 2 log ( x ) ) 2 ( x 2 log ( x ) ) = O ( x 4 )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?