High speed network traffic prediction is essential to provision QoS for multimedia applications while keeping bandwidth utilization high. Wavelet transform is a powerful technique for analyzing time domain signals. When combined with LMS, wavelet based predictor can achieve better performance than time domain predictor for MPEG-4 VBR videos and self-similar traffic. However, the computational complexity in predicting each wavelet coefficient is high. In this paper, LMK (Least Mean Kurtosis), which uses the negated kurtosis of the error signal as the cost function, is first proposed to estimate wavelet coefficients; then, by analyzing the wavelet coefficients of two consecutive data sets, Reduced Computation Complexity Wavelet LMK (RCCWLMK) is proposed to reduce the computational complexity. Simulation results for a wide range of MPEG-4 videos and network self-similar traffic show that RCCWLMK not only incurs smaller prediction error, but also reduces the computational complexity greatly.