Proving functions to be Big OhHow 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

Question

Proving functions to be Big OhHow 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

pyphekam · Accepted Answer

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  →  ∞

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

Answered question

Answer & Explanation

New Questions in Pre-Algebra