The　H.264　video　coding　standard　supports　several　inter-prediction　coding　modes　using　variable　block　sizes.　The　robust　rate-distortion　optimization　(RDO)　technique　of　both　the　motion　estimation　(ME)　and　the　mode　decision　(MD)　is　adopted　to　achieve　superior　coding　efficiency,　which　also　entails　a　lot　of　complex　computations.　In　this　paper,　by　rearranging　the　order　of　candidate　modes　and　using　two　new　rate-distortion-complexity　optimization　(RDCO)　functions,　a　more　efficient　RDCO　framework　for　fast　ME　and　MD　is　first　proposed.　Then,　with　this　new　framework,　a　novel　complexity　scalable　control　algorithm　for　H.264　inter-prediction　coding　is　devised,　which　is　based　on　an　efficient　complexity　allocation　and　control　(CAAC)　scheme　performed　both　at　the　frame　level　and　the　macroblock　(MB)　level.　Experimental　results　show　that　our　proposed　algorithm　can　adaptively　determine　an　appropriate　cut-off　point　for　a　sequence　of　re-ordered　candidate　modes　according　to　the　current　energy　condition　of　a　mobile　device,　which　can　adjust　the　complexity　of　inter-prediction　coding　to　any　appropriate　level　with　minimum　degradation　in　video　quality.　This　can　therefore　prolong　the　operational　lifetime　of　batteries.　(C)　2010　Elsevier　B.V.　All　rights　reserved.