Apriori estimation of quality of service (QoS) levels is a significant issue in e-services since Service Level Agreements (SLAs) need to specify and adhere to such estimates. Response time is an important metric for data intensive e-services such as data mining, data analysis and querying/information retrieval from large databases where the focus is on the time taken to present results to clients. A key component of response time in such data intensive services is the time taken to perform the computation, namely, the time taken to perform either data mining, analysis or retrieval. In this paper we present a novel approach for accurately estimating the computation times of data intensive e-services.