Continuous monitoring of audio-visual context on mobile devices requires algorithms with gentle demands on computational resources. Existing feature selection strategies for classification do not account for the complexity associated with feature extraction. We present a complexity-constrained feature selection algorithm that is independent of the classifier architecture and demonstrate that it leads to superior feature sets if the allowed computational complexity is limited.