Is log n T n log n

Question

I am to show that log n     T n  log n     A hint was given that I should show the upper bound with nn and show the lower bound with  n 2  n 2    This does not seem all that intuitive to me   Why would that be the case   I can definitely see how to convert nn to n  log n   i e  log both sides of an equation   but that s kind of working backwards     What would be the correct approach to tackle this problem   Should I draw the recursion tree   There is nothing recursive about this  so that doesn t seem like a likely approach

User · Answer

I realize this is a very old question with an accepted answer, but none of these answers actually use the approach suggested by the hint.

It is a pretty simple argument:

n! (= 1*2*3*...*n) is a product of n numbers each less than or equal to n. Therefore it is less than the product of n numbers all equal to n; i.e., n^n.

Half of the numbers -- i.e. n/2 of them -- in the n! product are greater than or equal to n/2. Therefore their product is greater than the product of n/2 numbers all equal to n/2; i.e. (n/2)^(n/2).

Take logs throughout to establish the result.

User · Answer

Remember that   log n     log 1    log 2          log n-1    log n    You can get the upper bound by   log 1    log 2          log n   lt   log n    log n          log n                                    n log n    And you can get the lower bound by doing a similar thing after throwing away the first half of the sum   log 1          log n 2          log n   gt   log n 2          log n                                            log n 2    log n 2 1          log n-1    log n                                          gt   log n 2          log n 2                                            n 2   log n 2

User · Answer

For lower bound   lg n     lg n  lg n-1      lg n 2      lg2 lg1         gt   lg n 2  lg n 2      lg n 2     n-1  2  lg 2  leave last term lg1  0   replace first n 2 terms as lg n 2   replace last  n-1  2 terms as lg2 which will make cancellation easier later           n 2 lg n 2     n 2  lg 2 - 1 2 lg 2          n 2 lg n -  n 2  lg 2    n 2 - 1 2          n 2 lg n - 1 2   lg n       1 2   n lg n - 1   Combining both bounds    1 2  n lg n - 1   lt   lg n    lt   n lg n  By choosing lower bound constant greater than  1 2  we can compensate for -1 inside the bracket   Thus lg n     Theta n lg n

User · Answer

This might help    eln x    x   and    lm n   lm n

User · Answer

Helping you further  where Mick Sharpe left you   It s deriveration is quite simple  see http   en wikipedia org wiki Logarithm -  Group Theory     log n     log n    n-1     n-2          2   1    log n    log n-1          log 2    log 1    Think of n as infinitly big  What is infinite minus one  or minus two  etc      log inf    log inf    log inf          inf   log inf    And then think of inf as n

User · Answer

Thanks  I found your answers convincing but in my case  I must use the T properties   log n     T n  log n    gt   log n     O n log n  and log n     O n log n    to verify the problem I found this web  where you have all the process explained  http   www mcs sdsmt edu ecorwin cs372 handouts theta n factorial htm

User · Answer

See Stirling s Approximation      ln n     n ln n  - n   O ln n     where the last 2 terms are less significant than the first one

User · Answer

Sorry  I don t know how to use LaTeX syntax on stackoverflow

User · Answer

http   en wikipedia org wiki Stirling 27s approximation Stirling approximation might help you  It is really helpful in dealing with problems on factorials related to huge numbers of the order of 10 10 and above

[algorithm] Is log(n!) = T(n·log(n))?

Examples related to algorithm

Examples related to math

Examples related to recursion

Examples related to complexity-theory

Examples related to big-o