# ExpOse: Inferring worst-case time complexity by automatic empirical study

### Kinneer, Cody and Kapfhammer, Gregory M. and Wright, Chris J. and McMinn, Phil

### Proceedings of the 27th International Conference on Software Engineering and Knowledge Engineering, 2015

### Abstract

A useful understanding of an algorithm’s efficiency, the worst-case time complexity gives an upper
bound on how an increase in the size of the input, denoted n, increases the execution time of the
algorithm, or f(n). This relationship is often expressed in the "big-Oh" notation, where f(n) is
O(g(n)) means that the time increases by no more than on order of g(n). Since the worst-case complexity
of an algorithm is evident when n is large, one approach for determining the big-Oh complexity of an
algorithm is to conduct a doubling experiment with increasingly bigger input sizes. By measuring the
time needed to run the algorithm on inputs of size n and 2n, the algorithm’s order of growth can be
determined. This paper introduces expOse, a tool to derive an "EXPerimental big-Oh" for supporting
"Scalability Evaluation" — expOse infers an algorithm’s big-Oh order of growth by conducting a
doubling experiment automatically.

### Resources

Paper

gkapfham/seke2015-tool-paper

kinneerc/ExpOse

### Reference

@inproceedings{Kinneer2015a,
author = {Kinneer, Cody and Kapfhammer, Gregory M. and Wright, Chris J. and McMinn, Phil},
title = {ExpOse: Inferring worst-case time complexity by automatic empirical study},
booktitle = {Proceedings of the 27th International Conference on Software Engineering and Knowledge Engineering},
year = {2015},
paper = {https://github.com/gkapfham/seke2015-tool-paper},
tool = {https://github.com/kinneerc/ExpOse}
}

Return to the List of Papers