Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages?E.g. linear search problem. We have an ordered set of incomparable elements (no < and >, equivalence only) of length $N$, and element for search – A, which could be in set maximum once. Set could be represented as sequence like 00001000, length $N$, where 1/0 means that element here equals A/not equals A. Algorithm parses the message and responds not contains (for one message 00000...0 ) and contains (all other messages). For uniform probability of being equal A for each position, entropy of responses equals:$$H=-\frac{1}{N+1}\cdot \log_2\left(\frac{1}{N+1}\right) - \frac{N }{N+1} \cdot \log_2\left(\frac{N}{N+1}\right)$$$H$ goes to zero quickly:We also know that $\lfloor\text{entropy}\rfloor+1$ equals the mean message length in case of best coding (Shannon's source coding theorem for symbol codes). That means we could index any message with binary string, and it will take us only one symbol – one step in algorithm! But existing codes for linear search (e.g. brute force) require $\frac{N+1}{2}>1$ steps, and all improved techniques require comparability (e.g. binary search).This suggests that entropy of message does not equal the number of step in best possible algorithm of problem solution (=message classification).But then what is the link between both? Is there any relationship between the number of steps for the abstract best code and the entropy of message?
Relationship between message entropy and complexity of the best algorithm
search algorithms;information theory;entropy