A novel approach to measure the complexity of human-computer interaction is presented. A complexity measure is defined, which relies on information-theoretic quantities such as block entropy. An efficient estimation procedure for the complexity measure is introduced. The estimation is based on variable length Markov chains and is using the well-known Shannon guessing game. The theoretical framework is validated by a study of user interaction with electronic map displays. The interaction task was to search for multiple vessel symbols under time pressure. 30 experienced master mariners participated as users. Samples from both users' visual scanpath and manual responses were acquired. The workload due to time pressure and the number of symbol clusters on the display were varied systematically. The results of an ANOVA (/spl alpha/=0.05) show a significant complexity decrease for manual response when the time pressure (or workload) is increased. The workload effect on the complexity of users' visual scanpath was stronger than on his manual response. The complexity of visual perception contributed to 85% of the overall complexity. There was also a significant effect of the number of symbol clusters on the display: a display with 2 clusters showed a significantly higher search complexity for manual response than a non-clustered display.