The very high complexity of the High Efficiency Video Coding standard (HEVC) is the main hurdle for its wide deployment and use. To tackle this problem, a number of recent research outcomes exploit Convolutional Neural Network (CNN) in each HEVC module for reducing the coding complexity. In this paper an effective method to analyse the potential of CNN techniques to reduce the computational cost of HEVC is proposed. A theoretical upper bound for the effectiveness of this approach in common HEVC modules is investigated. The theoretical maximum of learning-based complexity reduction in HEVC and possible reasons for Rate-Distortion (RD) loss are investigated. On the basis of this analysis, an Intra Video Coding Acceleration (IVCA) scheme is proposed, where Border Considered CNN (BC-CNN) based Coding Unit (CU) partition and heuristic Prediction Unit (PU) partition are seamlessly integrated. According to the experimental results, 66.7% of intra coding time can be saved with negligible 1.71% Bjøntegaard delta bit-rate (BDBR) loss. These results partially demonstrate the superiority of the proposed technique against other state-of-the-art approaches aiming at reducing HEVC complexity in intra mode.