Component-based software construction is a widely used approach in software development, aiming to reduce the engineering effort and speed up development cycle. During software maintenance, various software update approaches can be utilized to realize specific change requirements of component-based software. Different update approaches might lead to diverse regression testing complexity. However, there is a lack of research work addressing regression testing complexity in software maintenance. In this paper, a framework is proposed to measure and analyze regression testing complexity based on a set of change and impact complexity models and metrics. The paper presents an approach to complexity metrics for regression testing of component-based software. A graphic model and several measurements for the complexity metrics, which consist of both maintenance and retesting complexity, are also proposed. An experimental study is conducted to compare the complexity of regression testing using the data from several independent groups. The study results indicate the presented approach is feasible in providing visual comparison on various complexity of regression testing from different methods.