Simulating Average Time Complexity Of SRSWOR: A Statistical Approach
by
Anchala Kumari
Department of Statistics, Patna University, Patna-80005, India.
Coauthors: Soubhik Chakarborty (University Department of Statistics and Computer Applications, T.M.Bhagalpur University, Bhagalpur-812007 INDIA)

An algorithm is fundamental concept to computer science.Developing an optimal algorithm for solving a problem depends on its computational complexity:a characterization of time or space requirement by a particular algorithm and provides a quantitative judgement to select the best algorithm.

Lot of work has been done to measure the computational comlexity but none of them is realistic in nature as these measures express the order of comlexity by computing the minimum number of operations required or in turn as the function of input parameter.

In this paper we have focused on statistical approach to simulate the average complexity of an algorithm .The method has been illustrated by finding the average time complexity of Simple Reandom Sample Without Replacement Where the samle size n is taken to be the squre root of population size N.

Interestingly, for large N, an emprical lower bound than theoretical l.u.b is obtained for the complexity, which is very realistic.We have also obtained the estimates of the parameters. The emphasis has been given on pattern recognition than on estimation since the estimates are system dependent.

Date received: November 29, 2004