If f ( n ) = ( n ) n and g ( n ) = ( lg ⁡ n ) n , is f ( n ) = O ( g ( n ) ) or g ( n ) = O ( f ( n ) )?

Question

If   f  (  n  )  =  (      n        )                  n             and   g  (  n  )  =  (  lg  ⁡  n      )    n  , is   f  (  n  )  =  O  (  g  (  n  )  ) or   g  (  n  )  =  O  (  f  (  n  )  )?

Shiloh Davenport · Accepted Answer

The answer is g grow faster.We can take the ratio between the two and get:      (                  f        (        n        )                    g        (        n        )              )    =      (                            n                          n                            lg        ⁡                  n          n                      )    =      (                  n                              n                                /                    2                            lg        ⁡                  n          n                      )    =            (                        n                                    1              2                                                lg          ⁡                      n                          n                                          )              n      And this is clear that after some point(if lg is base 10 then after 24.13...) we have             n                        1          2                            lg      ⁡              n                  n                      &amp;lt;  1 thus   f  (  n  )  =      O    (  g  (  n  )  )The reason for this is that before the functions logarithmic or polynomial they are exponential, which is growing faster than both of the above, and in this exponential we have g(n) grow exponentially faster than f(n), so even if in g we have log growing and in f we have polynomial growing the log growing exponentially in compare to the polynomial and the polynomial growing linearly

If f(n)=(sqrt(n))^(sqrt(n)) and g(n)=(lg n)^n, is f(n)=O(g(n)) or g(n)=O(f(n))?

Answered question

Answer & Explanation

New Questions in Calculus 1