# 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? – phant0m Jul 30 '12 at 16:22
@phant0m I already provided the link to that function . – 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. – Pieter B 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. – phant0m Jul 30 '12 at 17:11

## 1 Answer

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? – phant0m Jul 31 '12 at 9:13
yes it does. Thanks for the refresher again. – Geek Jul 31 '12 at 9:15
@Geek: You're welcome ;) – phant0m Jul 31 '12 at 9:17