Proving functions to be Big Oh How do I determine if there exists a function f , such that

Emmy Knox

Emmy Knox

Answered question

2022-06-11

Proving functions to be Big Oh
How do I determine if there exists a function f, such that
f ( n ) = O ( log n ) ,
but
2 f ( n ) O ( n ) .
Is true or false?
I tried using the c and No method but cannot come up with a solution

Answer & Explanation

pyphekam

pyphekam

Beginner2022-06-12Added 27 answers

Here is a counterexample:
Take f ( n ) = k log n = log n k , where k = 2 log 2 . Then clearly, f ( n ) = O ( log n )
At the same time
2 f ( n ) = 2 log n k = e ( k log 2 ) log n = e 2 log n = e log n 2 = n 2 ,
but the function 2 f ( n ) = n 2 is definitely not O ( n ), as
2 f ( n ) n ,
when n

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

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

Didn't find what you were looking for?