Parameterized Complexity of Partition Sort for Negative Binomial Inputs

International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN. International E-Bulletin: Information/News regarding: Academics and Research

Parameterized Complexity of Partition Sort for Negative Binomial Inputs

Author Affiliations

¹Department of Computer Science and Engineering, B.I.T. Mesra, Ranchi-835215, INDIA
² Department of Applied Mathematics, B.I.T. Mesra, Ranchi-835215, INDIA

Res. J. Engineering Sci., Volume 1, Issue (5), Pages 12-16, November,26 (2012)

Abstract

The present paper makes a study on Partition sort algorithm for negative binomial inputs. Comparing the results with those for binomial inputs in our previous work, we find that this algorithm is sensitive to parameters of both distributions. But the main effects as well as the interaction effects involving these parameters and the input size are more significant for negative binomial case.

References

Singh N.K., and Chakraborty S., Partition Sort and its Empirical Analysis, V.V. Das and N. Thankachan (Eds.): CIIT 2011, CCIS 250, 340–346, 2011, © Springer-Verlag Berlin Heidelberg (2011)
Sourabh S.K. and Chakraborty S., How robust is quicksort average complexity? arXiv:0811.4376v1 [cs.DS], Advances in Mathematical Sciences Jour. (to appear)
Singh N.K., Pal M. and Chakraborty S., Partition sort revisited: Reconfirming the robustness in average case and much more, International Journal on Computer Science, Engineering and Applications, 2(1), 23-30 (2012)
Chakraborty S. and Sourabh S.K., A Computer Experiment Oriented Approach to Algorithmic Complexity, Lambert Academic Publishing (2010)
Fang K.T., Li R. and Sudjianto A., Design and Modeling of Computer Experiments, Chapman and Hall (2006)
Sacks J., Weltch W., Mitchel T. and Wynn H., Design and Analysis of Computer Experiments, Statistical Science,4(4), (1989)
Downey R.G. and Fellows M.R., Parameterized Complexity, Springer (1999)
Mahmoud H., Sorting: A Distribution Theory, John Wiley and Son (2000)
Chakraborty S., Sourabh S.K., Bose M. and Sushant K., Replacement sort revisited: The “gold standard” unearthed!, Applied Mathematics and Computation, 189(2), 384-394 (2007)

[ref1] Singh N.K., and Chakraborty S., Partition Sort and its Empirical Analysis, V.V. Das and N. Thankachan (Eds.): CIIT 2011, CCIS 250, 340–346, 2011, © Springer-Verlag Berlin Heidelberg (2011)

[ref2] Sourabh S.K. and Chakraborty S., How robust is quicksort average complexity? arXiv:0811.4376v1 [cs.DS], Advances in Mathematical Sciences Jour. (to appear)

[ref3] Singh N.K., Pal M. and Chakraborty S., Partition sort revisited: Reconfirming the robustness in average case and much more, International Journal on Computer Science, Engineering and Applications, 2(1), 23-30 (2012)

[ref4] Chakraborty S. and Sourabh S.K., A Computer Experiment Oriented Approach to Algorithmic Complexity, Lambert Academic Publishing (2010)

[ref5] Fang K.T., Li R. and Sudjianto A., Design and Modeling of Computer Experiments, Chapman and Hall (2006)

[ref6] Sacks J., Weltch W., Mitchel T. and Wynn H., Design and Analysis of Computer Experiments, Statistical Science,4(4), (1989)

[ref7] Downey R.G. and Fellows M.R., Parameterized Complexity, Springer (1999)

[ref8] Mahmoud H., Sorting: A Distribution Theory, John Wiley and Son (2000)

[ref9] Chakraborty S., Sourabh S.K., Bose M. and Sushant K., Replacement sort revisited: The “gold standard” unearthed!, Applied Mathematics and Computation, 189(2), 384-394 (2007)