In master method they talk about functions being asymptotically
larger and polynomialy larger. But I don't feel much difference
between them. What are their definitions ? And in one case they
say nlog2(n) is asymptotically larger than n but is not
polynomialy larger than n . The reason they have given is that
nlog(n)/n = log(n) is asymptotically less than n^e for any
positive constant e. But for me the last part seems incorrect.
Because for 0<e< 0.2 n^e is asymptotically smaller than log(n).
Am I correct? Please help me. the whole asymtoticaly and
polynominal-thing is much more show than really substance. There
are a few Functions between log and polonoms and exp, but almost
none of them has some real impact. (ok... maybe the iterated
logarithm is sometimes important) (thats my opinion) For your
question x^0.1 grows much faster than log(x). Just type very big
numbers in your calculator. x^0.01 also grows faster than
log(x). This is not a proof, just try around to get a feeling.
The proof for this goes like th