Microsoft Interview Question
Software Engineer / DevelopersAlmost, except 2^n isn't asymptotically greater than n^100
You can easily see this when you take the log(base2) of n^100 and 2^n.
log(base2)(n^100) == 100 * log(base2)(n)
log(base2)(2^n) == n * log(base2)(2) == n
Obviously 100 * log(base2)(n) > n for any value of n > 1 and consequently n^100 is > 2^n for any n > 1.
Therefore the correct ordering is the following:
n^n
n!
n^100
2^n
Almost Michael, except that 100*log_2(n) < n for reasonably large n in fact take n > 2^10. What did you do? check for a few values and make an "obvious" generalization?
btw, do you realize that you indirectly have claimed that P = NP?
You need to brush up on your Math.
btw, why is this under Terminology & Trivia? Don't we have a section for Basics?
n^100
- sriram July 02, 20082^n
n!
n^n