Extremal sequences of polynomial complexity