Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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
up vote 7 down vote accepted

In short: a smaller(bigger) exponent of n.

It relates directly to a part of my answer to an earlier question of yours here:

formula, 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: enter image description here

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":

polynomially smaller formula

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:

enter image description here

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.