Polynomial with the natural coefficients is given as a black box (you can choose any $p>0$ and evaluate it in $\mathbb{Z}_p$ in time $O(\log(p))$) Moreover, we know that the degree of black box polynomial is bounded by n.
Can we determine the degree of polynomial in randomized time $o(n)$.
We can take values $$P_0(i)=P(i), i=0\dots n,$$ and to calculate differences $$P_k(j)=P_{k-1}(j+1)-P_{k-1}(j), j=0\dots n-k-1$$ until all $P_k(j)$ became constants.
It is easy to prove that all $P_k=const$ for $k$th order polynomial.