Long term memory motion compensation (LTMC) is an approach to extend the temporal motion search range by using multiple decoded frames as reference frames. By employing multiple reference frames, LTMC reduces the residual frame energy significantly. However the computational complexity of motion estimation for LTMC increases significantly as well. Therefore reduction of the required computational complexity is one of the most challenging issues for LTMC. Also, if we locate motion search windows at fixed locations in a frame buffer for a given macro-block, it is highly possible that the oldest frames in a frame buffer do not contain matching blocks due to the reduced correlation between the current frame and the reference frames located further in the frame buffer. Therefore, if we can locate the motion search window at a good position adaptively in a frame buffer, we can enhance the gain performance of LTMS. In this paper, we propose a novel motion estimation algorithm for LTMC to reduce significantly the required computation complexity, and to enhance the performance of LTMC. For the proposed motion estimation algorithm, we introduce a directed search strategy. Also, we propose to employ hypothesis testing fast matching (HTFM) as a fast matching criterion. The goal of a directed search strategy is to let the location of the motion search windows change adaptively as the search proceeds to older frames in the frame buffer. The main benefit over standard, fixed window, approaches is that the algorithm can track larger motion and therefore, we can reduce the residual frame energy. In addition, because the directed search strategy keeps track of best matched blocks, we can reduce the computational complexity significantly by reducing the motion search window area in a frame buffer. Simulation results show that by employing the directed search with reduced motion search window, we can reduce the computational complexity approximately 30%-40%, and that by employing HTFM, we can reduce the computational complexity as additional 40%-50% as compared to the result of a full search algorithm which employs a non-directed search strategy for LTMC. The proposed algorithm provides particularly significant gains for video sequences which contain large motions. In the case of high motion sequences directed search also results in slight gains in PSNR over non-directed search.