The paper presents analysis and comparison of complexity of selected algorithms of motion estimation used in video compression. With the use of own, highly optimized software implementation the authors explored complexity of the methods applied in the framework of the new High Efficiency Video Compression (HEVC) technology. The influence of many different factors on motion estimation complexity has been deeply studied, including the implementation technique, type of the algorithm, number of processor threads used, kind of metric of blocks similarity. The results obtained allowed to formulate guidelines and conclusions that may be useful for future implementation of motion estimation algorithms in context of HEVC encoders.