In this letter, a new fast motion estimation (FME) algorithm capable of producing sub-sample motion vectors at low computational-complexity is proposed. Unlike existing FME algorithms, the proposed algorithm considers the low complexity sub-sample accuracy in designing the search pattern for FME. The proposed FME algorithm is designed in such a way that the block distortion measure is modeled as a parametric surface in the vicinity of the integer-sample motion vector; this modeling enables low computational-complexity sub-sample motion estimation (ME) without pixel interpolation. Experimental results on video test sequences show that the proposed FME algorithm reduces computational complexity of integer and sub-sample ME considerably compared with traditional methods at the cost of negligible performance degradation.