Finite length sequences with large nonlinear complexity

Finite length sequences with large nonlinear complexity over \begin{document}$\mathbb{Z}_{p}\, (p≥ 2)$\end{document} are investigated in this paper. We characterize all \begin{document}$p$\end{document} -ary sequences of length \begin{document}$n$\end{document} having nonlinear complexity \begin{document}$n-j$\end{document} for \begin{document}$j=2, 3$\end{document} , where \begin{document}$n$\end{document} is an integer satisfying \begin{document}$n≥ 2j$\end{document} . For \begin{document}$n≥ 8$\end{document} , all binary sequences of length \begin{document}$n$\end{document} with nonlinear complexity \begin{document}$n-4$\end{document} are obtained. Furthermore, the numbers and \begin{document}$k$\end{document} -error nonlinear complexity of these sequences are completely determined, respectively.