I was going over this video lecture on master theorem from Introduction to Algorithm and while explaining case A of the master theorem professor says that some function f(n) is polynomially smaller than some other function at point 53:08 seconds:
What does it mean for a function to be polynomially smaller than this function?
I am confused here as polynomially is not equivalent to poly-logarithmically. Has the professor used the wrong term here ? It is highly unlikely though since he goes on to say the same term a number of times.
6
In short: a smaller(bigger) exponent of n.
It relates directly to a part of my answer to an earlier question of yours here:
, which basically says that n to some power grows faster, if the exponent is bigger, regardless of constant factors.
In case 1, function f(n) is assumed to be polynomially smaller than this one:
Don’t get scared by the logarithm here, it is just a number, because a and b are constants, so is log_b(a). (Which is why poly-logarithmically does not enter the picture, in that case)
It is then defined to what class of functions f(n) must belong to. This is already the answer to your question "what it means to be polynomially smaller":
All it means is, that the exponent of n must be less than log_b(a): You subtract a positive number (epsilon) from it.
This is another way of looking at it:
The polynomially bigger one has more factors of n: epsilon more. (or less in the case of smaller)
At 57:30 he gives an example, where he ends up in case 1: He compares f(n) = n with n^2. f(n) is polynomially smaller because 1 < 2.
3