hp home products & services support solutions how to buy
hp logo - invent
corner hp labs corner
search search
contact hp contact hp
hp labs home hp labs home
about hp labs about hp labs
research research
news and events news and events
careers @ labs careers @ labs
technical reports technical reports
talks and speeches talks and speeches
worldwide sites worldwide sites
corner corner
HP Labs Technical Reports

Click here for full text: Postscript PDF

Entropy and Complexity

Shah, Devavrat; Sharma, Mayank


Keyword(s): information theory; algorithms

Abstract: Computational complexity of algorithms for solving problems has been at the heart of theoretical computer science. Traditionally, the computational cost of an algorithm is estimated by "counting" operations combinatorially depending on the algorithm. We present a very different method for estimating cost of solving problem, incorporating ideas from information theory. Algorithms can be viewed as "search" procedures on the input (output) space. This naturally makes computational cost of algorithm as function of "entropy" of input (output) distribution. The relation of computational complexity and "entropy" of distribution depends on the particular "operations" used by algorithm to solve problem. This particular mapping between computational scale and "entropy" scale is independent of problem. We demonstrate the use of this method in classical "searching" and "sorting" problems. We work out many different searching and sorting algorithms' complexity using this method. In process, we also come up with new algorithms to solve some cases of searching and sorting that are aware of input distribution.

16 Pages

Back to Index

printing icon
printing instructions printing instructions
Privacy Statement Legal Notices © 1994-2000 Hewlett-Packard Company