Complexity of the EQUATE testing strategy
Abstract Most testing methods do not fare well with software whose modules contain data and operations at widely varying levels of abstraction. With the evolution of new design techniques and new languages that encourage the use of more abstract data types, it is becoming increasingly important that testing methods begin to deal with abstraction in a reasonable and consistent manner. The EQUATE testing strategy offers strong support for data and functional abstraction. EQUATE selects a number of test locations throughout the program and chooses a set of expressions derived from the abstract syntax tree of the module being tested. Test data is required that distinguishes these expressions from one another at every test location. The time complexity of EQUATE is at worst O(Lp2) and the space complexity O(Lp3) where Lp is the length of the program under test.