La description de chaque opération doit donner une indication de sa performance, concernant en particulier le temps de calcul, mais aussi la consommation de mémoire. Ces descriptions peuvent éventuellement être omises s'il est clair que l'opération est efficace. En particulier, si l'opération appartient à un type abstrait bien connu et que son comportement est bien connu aussi, il n'est pas nécessaire d'inclure ces descriptions. Un exemple est l'opération pour enfiler un objet dans une file. Si le type abstrait est bien programmé, cette opération doit être exécutée en O(1) avec très peu d'instructions et ne doit pas allouer beaucoup de mémoire.
Par contre, pour les types abstraits moins connus ou les types abstraits spécifiques à l'application, il est important de documenter la performance.
La description d'une opération doit contenir un indication de la complexité asymptotique au pire. Cette information est importante pour le programmeur consommateur afin qu'il puisse estimer le temps de calcul de l'application dans le pire des cas.
Mais la complexité asymptotique ne suffit pas à décrire la performance. D'abord, il est utile d'inclure une indication concernant la constante multiplicative de la complexité. Ensuite, il n'est pas sûr que les cas les pire arrivent souvent en pratique. C'est le cas en particulier de certains algorithmes comme le tri rapide dont la complexité asymptotique est O(n2) mais qui est très rapide en pratique, et la méthode du simplexe qui est exponentielle au pire, mais qui est pourtant l'algorithme le plus rapide qui fonctionne pour la programmation linéaire. C'est aussi le cas quand la performance dépend d'un motif d'utilisation. La gestion du tampon de l'éditeur Emacs est par exemple relativement coûteuse si l'on regarde la complexité asymptotique. Mais pour toute utilisation normale, elle est très rapide.
Par conséquent, il est utile d'indiquer dans la description d'une opération tous les aspects de la performance, afin d'assister le programmeur consommateur dans son choix.