# What does it mean when we say that some function is polynomially bigger/smaller than some other function?

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.

• Can you give the functions in your post? Jul 30 '12 at 16:22
– Geek
Jul 30 '12 at 16:23
• I think the professor meant that one algorithm scales better then the other. Once things get more complex, the slower algorithm will perform worse and worse then the better one. Jul 30 '12 at 16:32
• note professor uses wording "polynomially smaller / larger" (screen shot). Searching the web for this wording yields interesting results (eg 1, 2)
– gnat
Jul 30 '12 at 17:06
• Yes, but it's much better if you include all necessary information in your post, not just link to it. Jul 30 '12 at 17:11

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`.

• What is log_b(a) ? What does underscore and () signify ? What is the base here ?
– Geek
Jul 31 '12 at 3:36
• log_b(a) means log to the base b of a ?Still confused with the underscore .
– Geek
Jul 31 '12 at 7:52
• @Geek Exactly. The underscore is used to indicate subscript. Does that help? Jul 31 '12 at 9:13