As more and more flexible block modes are introduced into video coding, mode decision technology becomes an important coding tool. The performance of mode decision has great impact on both coding performance and computational complexity. This article proposes a complexity controllable multi-mode decision algorithm to attain optimized coding performance under different computational complexity constraints herein. Instead of speeding up multi-mode decision merely, the algorithm predicts the Lagrangian cost and complexity slope (J-C slope) of MD for each macroblock (MB) by exploiting their temporal and spatial correlations. The larger J-C slope is, the higher coding gain over each unit of computational cost will be. In the environment of limited computational resources, multi-mode decision should be performed in a cost effective order, i.e. the order of their J-C slopes, to achieve optimized coding performance. In addition, an adaptive method is proposed to adjust the computational complexity of the algorithm dynamically by discovering the relationship of J-C slope thresholds and their corresponding complexity. Experiments demonstrate the proposed algorithm can both precisely adjust the computational complexity and optimally perform mode decision under different computational constraints.