arrays the classdataarray java program shows that class objects can be handled by data storage structures in much the same way as primitive types (note that serious program using the last name as key would need to account for duplicate last nameswhich would complicate the programming as discussed earlier big notation automobiles are divided by size into several categoriessubcompactscompactsmidsizeand so on these categories provide quick idea what size car you're talking aboutwithout needing to mention actual dimensions similarlyit' useful to have shorthand way to say how efficient computer algorithm is in computer sciencethis rough measure is called "big onotation you might think that in comparing algorithms you would say things like "algorithm is twice as fast as algorithm ,but in fact this sort of statement isn' too meaningful why notbecause the proportion can change radically as the number of items changes perhaps you increase the number of items by %and now is three times as fast as or you have half as many itemsand and are now equal what you need is comparison that tells how an algorithm' speed is related to the number of items let' see how this looks for the algorithms we've seen so far insertion in an unordered arrayconstant insertion into an unordered array is the only algorithm we've seen that doesn' depend on how many items are in the array the new item is always placed in the next available positionat [nelems]and nelems is then incremented insertion requires the same amount of time no matter how big --the number of items in the array--is we can say that the timetto insert an item into an unsorted array is constant kt= in real situationthe actual time (in microseconds or whateverrequired by the insertion is related to the speed of the microprocessorhow efficiently the compiler has generated the program codeand other factors the constant in the preceding equation is used to account for all such factors to find out what is in real situationyou need to measure how long an insertion took (software exists for this very purpose would then be equal to that time linear searchproportional to we've seen thatin linear search of items in an arraythe number of comparisons that must be made to find specified item ison the averagehalf of the total number of items thusif is the total number of itemsthe search time is proportional to half of nt= * /