To determine the best block mode among the different sizes in H.264/AVC, the rate distortion cost is used as a determining factor. This process requires relatively large amount of computation to encounter all the combinations of different sizes of MBs. In this paper, a new fast inter-mode decision algorithm is proposed in this context. The proposed method reduces the number of candidate modes using direct information from the co-located macroblock(s). A novel motion complexity analysis scheme is also discussed in this paper which is strong enough to categorize different moving objects inside a MB and to make a proper decision for the best candidate mode. Experiment results show that the proposed algorithm can achieve speed-up factor up to 78.70% on average with negligible loss of image quality and quite good bit rate performance.