CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
Simon Leung
Simon Leung

Reputation: 25

Big O simplification of factorial

To calculate BigO and constant for the following function : I have don't know how to simplify it further. Any advise ? Thx

 T(n) =  (n!n+n^3)(n^2+7logn)      
      <= (n!n+n^3)(n^2 +7n)   (since n>= log n)
      <= (n!n+n^3)(n^2 +7n)    (n^3 >= 7n if n > 3) 
      <= (n!n+n^3)(n^2 + n^3)   
      <= (n!n+n^3)(n!n + n^3)  (n!n >= n^2)    
         :

Upvotes: 1

Views: 310

Answers (1)

Patrick87
Patrick87

Reputation: 28312

The highest-order term can be found by expanding:

 T(n) =  (n!n+n^3)(n^2+7logn) 
      =  n!n^3 + 6n!nlogn + n^5 + 7n^3logn

At this point we can simply compare terms and see which one is biggest:

n!n^3 vs 6n!nlogn
since n^2 > 7logn for n >= 4, n!n^3 > 7n!nlogn for n >= 1

n!n^3 vs n^5
since n! > n^2 for n >= 4, n!n^3 > n^5 for n >= 4

n!n^3 vs 7n^3logn
since n! > 7logn for n >= 4, n!n^3 > 7n^3logn for n >= 4

Based on all this, for n >= 4,

 T(n) =  (n!n+n^3)(n^2+7logn) 
      =  n!n^3 + 6n!nlogn + n^5 + 7n^3logn
     <=  n!n^3 + n!n^3 + n!n^3 + n!n^3
      = 4n!n^3
      = O(n!n^3)

If you want to find another expression that bounds n!n^3 that's well and good, but I'd recommend another question for that.

Upvotes: 1

Related Questions