This paper presents a novel and generic algorithm for reduction in computational complexity associated with the estimation of LS based predictor. Many lossless compression algorithms used predictor based on Least Squares and its variance for decorrelation of images. However, computational complexity associated with estimation of such predictor is huge. So, in order to reduce the computational complexity, we proposed to estimate a LS based predictor of order p-1 and estimates the coefficients of predictor of order p. We have reduced the predictor order form p to (p - 1) that results into a saving of computational power. We have also reduced the predefined error threshold in EDP and RALP algorithm in order to negotiate the slight loss in prediction accuracy due to synthetically generated prediction coefficient. The proposed algorithm is generic that can be used with most of the LS based lossless compression algorithms reported in literature. Our proposed algorithm gives same prediction quality as compared to when we use the actual prediction coefficient and there is around 25% to 40% reduction in computational complexity. © 2011 IEEE.