A complexity scalable device (100), method (300, 400) and digital video encoder (200) estimate a frame-to-frame motion vector of an image block of pixels to be encoded with adaptive threshold termination utilizing a novel dynamic threshold value determination. A dynamic threshold selector dynamically determines a threshold value in accordance with a predetermined scheme based on the quantization stepsize QP, and an adaptive motion vector determiner utilizes an original block, a reference frame, and the threshold value for adaptively estimating the frame-to-frame motion vector.