MPEG-2 and MPEG-4 are two most popular international video compression standards. They will coexist in different systems and networks for a long time. For compatibility of these two video standards, this paper put forward three transcoding algorithms on the basis of detailed analysis of computational complexity. In the paper, the principle and implementation of two efficient transcoding algorithms are emphasized. Both of them are tradeoff between the computational complexity and reconstructed video quality. One is motion-information reusing algorithm, which meets the highest video quality requirement of studio and post-processing environments. The other is real-time low complexity transcoding algorithm, which is proper for low delay requirement of the network server and user terminal with limited computational performance. The simulation results of many test sequences verified the high performance of the algorithms.