algorithm analysis in classic storythe famous mathematician archimedes was asked to determine if golden crown commissioned by the king was indeed pure goldand not part silveras an informant had claimed archimedes discovered way to perform this analysis while stepping into bath he noted that water spilled out of the bath in proportion to the amount of him that went in realizing the implications of this facthe immediately got out of the bath and ran naked through the city shouting"eurekaeureka!for he had discovered an analysis tool (displacement)whichwhen combined with simple scalecould determine if the king' new crown was good or not that isarchimedes could dip the crown and an equal-weight amount of gold into bowl of water to see if they both displaced the same amount this discovery was unfortunate for the goldsmithhoweverfor when archimedes did his analysisthe crown displaced more water than an equal-weight lump of pure goldindicating that the crown was notin factpure gold in this bookwe are interested in the design of "gooddata structures and algorithms simply puta data structure is systematic way of organizing and accessing dataand an algorithm is step-by-step procedure for performing some task in finite amount of time these concepts are central to computingbut to be able to classify some data structures and algorithms as "good,we must have precise ways of analyzing them the primary analysis tool we will use in this book involves characterizing the running times of algorithms and data structure operationswith space usage also being of interest running time is natural measure of "goodness,since time is precious resource--computer solutions should run as fast as possible in generalthe running time of an algorithm or data structure operation increases with the input sizealthough it may also vary for different inputs of the same size alsothe running time is affected by the hardware environment ( the processorclock ratememorydiskand software environment ( the operating systemprogramming languagein which the algorithm is implemented and executed all other factors being equalthe running time of the same algorithm on the same input data will be smaller if the computer hassaya much faster processor or if the implementation is done in program compiled into native machine code instead of an interpreted implementation we begin this by discussing tools for performing experimental studiesyet also limitations to the use of experiments as primary means for evaluating algorithm efficiency focusing on running time as primary measure of goodness requires that we be able to use few mathematical tools in spite of the possible variations that come from different environmental factorswe would like to focus on the relationship between the running time of an algorithm and the size of its input we are interested in characterizing an algorithm' running time as function of the input size but what is the proper way of measuring itin this we "roll up our sleevesand develop mathematical way of analyzing algorithms