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 method 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 (as reflected in the processorclock ratememorydisketc and software environment (as reflected in the operating systemprogramming languagecompilerinterpreteretc in which the algorithm is implementedcompiledand 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 run on virtual machine neverthelessin 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 itexperimental studies if an algorithm has been implementedwe can study its running time by executing it on various test inputs and recording the actual time spent in each execution fortunatelysuch measurements can be taken in an accurate manner by using system calls that are built into the language or operating system (for exampleby using the system current time millis (method or calling the run-time environment with profiling enabledsuch tests assign specific running time to specific input sizebut we are interested in determining the general dependence of running time on the size of the input in order to determine this dependencewe should perform several experiments on many different test inputs of various sizes then we can visualize the results of such experiments by plotting the performance of each run of the algorithm as point with -coordinate equal to the input sizen