Abstract De Bruijn sequences are highly important nonlinear shift register sequences. The homogeneous complexity Ck(ε) of degree κ of a De Bruijn sequence ε is defined and discussed. Its upper bound is given. The linear complexity and the quadratic complexity are special cases of Ck(ε) for k=1 and k= 2 respectively.