In this paper, we propose a representation selection optimization problem for complexity constrained adaptive video streaming that properly takes into account the different complexity-rate-distortion (C-R-D) characteristics of the videos when implementing rate control for desired representations. Our objective is to maximize the expected video distortion reduction of users, subject not only to encoding rate constraints, but also to complexity constraints. We prove that our optimization problem is a submodular maximization problem with two knapsack constraints. A weighted rate and complexity cost benefit greedy algorithm is then developed to obtain an approximate solution with polynomial time complexity and good approximation performance in simulations.