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

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.

  • 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
  • 1
    @Geek Exactly. The underscore is used to indicate subscript. Does that help?
    – phant0m
    Jul 31 '12 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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