1

I'm learning a MIT Session about computation complexity

At about 6:26 into the video linked above, the speaker says "basically, we look over here at the polynomial function." The link starts at 6:21.

enter image description here

A polynomial function is usually in this form

$f(x)= a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}$

where n is a non-negative integer and a0, a1, a2, ..., an are constant coefficients.

When considering $$f(n) = n \log n$$ a polynomial function, there is only one term which has a coefficient of 1. Is my understanding correct?

I know how to count the degree of a regular polynomial function. For example, the degree of the polynomial function $f(x) = 5x^{2} + x$ is 2.

What's the degree of the polynomial function $f(n) = n \log n$?

A few seconds later, the speaker says "… the log factor is smaller than a polynomial factor." I guess "the log factor" refers to $\log n$ though I can't even make a guess about what "polynomial factor" refers to.

JJJohn
  • 1,436
  • 3
    It is not a polynomial but it behaves like polynomials when it comes to speed of growth, which is what matters here. The key word is "basically". – Michal Adamaszek Feb 22 '22 at 11:33
  • It sure is larger than one, but I reckon that it would be smaller than any number larger than one. – user Feb 22 '22 at 11:34
  • 1
    For computational complexity you're looking at bounds for the function given input size and $n \log n$ can be bounded by polynomials, meaning it's in the same complexity class as polynomials. It is however not a polynomial, they just live in the same building. – CyclotomicField Feb 22 '22 at 11:59

1 Answers1

3

I've watched few minutes of that video, and the explanation here is indeed a bit messy.

Lets make things clear first: $n\log n$ is not a polynomial function.

But it does have polynomial factor and logarithmic factor. The lecturer wants to explain why it grows slower than $n^2\log n^{2019}$ and $n^3$. He starts with "if we factor $n$ out of that then we're comparing $\log$ with a, you know..." and he seems to be lost for a second (which is a pity, I think that was a correct start). Then he restarts with the "basically, we look over here at the polynomial function". But I think he was refering to the polynomial factor of $f_5$ here, not entire $f_5$ (his hand is even directly over $n$). Because then he says: "this one" (I assume he refers to $n$) "is the smallest out of them" (I think he refers to polynomial pieces of other functions) and finally he says: "and the $\log$ factor grows slower than linear" making $n\log n$ smaller than $n^2\log n^{2019}$ and $n^3$.

I don't see any other logical explanation of his words.

freakish
  • 42,851
  • Thank you. A few seconds later, the speaker says "… the log factor is smaller than a polynomial factor." I guess "the log factor" refers to $\log n$ though I can't even make a guess about what "polynomial factor" refers to. – JJJohn Feb 22 '22 at 12:21
  • 3
    @JJJohn given $n\log n$ it is composed of polynomial factor $n$ and logarithmic factor $\log n$. Given $n^2\log n^{2019}$ it has polynomial factor $n^2$ and logarithmic factor $\log n^{2019}$. Given $n^3$ it has polynomial factor $n^3$ and logarithmic factor $1$ (or you can say it has no logarithmic factor). But I agree, his explanation is sloppy. – freakish Feb 22 '22 at 12:21
  • 1
    @JJJohn $n$ is a polynomial. We tend to forget because it's linear but it counts. – CyclotomicField Feb 22 '22 at 13:27