6

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:

formula

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.

phant0m
  • 2,614
  • 16
  • 25
Geek
  • 5,107
  • 8
  • 40
  • 58
  • 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](http://i.stack.imgur.com/rxTJj.png)). Searching the web for this wording yields interesting results (eg [1](http://math.stackexchange.com/questions/37332/asymptotically-larger-vs-polynomially-larger), [2](http://stackoverflow.com/questions/5931657/polynomially-larger-confusion)) – 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
  • btw, he mentions that you need `"divine inspirations"` to guess closed forms for these recurrences, but you can also figure it out systematically (30:30) - at least for the formula that he's working on it's quite simple. – phant0m Jul 30 '12 at 18:52

1 Answers1

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.

Community
  • 1
phant0m
  • 2,614
  • 16
  • 25