divided by now we have this says that average linear search times are proportional to the size of the array if an array is twice as bigit will take twice as long to search binary searchproportional to log(nsimilarlywe can concoct formula relating and for binary searcht log (nas we saw earlierthe time is proportional to the base logarithm of actuallybecause any logarithm is related to any other logarithm by constant ( to go from base to base )we can lump this constant into as well then we don' need to specify the baset log(ndon' need the constant big notation looks like these formulasbut it dispenses with the constant when comparing algorithms you don' really care about the particular microprocessor chip or compilerall you want to compare is how changes for different values of nnot what the actual numbers are thereforethe constant isn' needed big notation uses the uppercase letter owhich you can think of as meaning "order of in big notationwe would say that linear search takes (ntimeand binary search takes (log ntime insertion into an unordered array takes ( )or constant time (that' the numeral in the parentheses table running times in big notation algorithm running time in big notation linear search (nbinary search (log ninsertion in unordered array ( insertion in ordered array (ndeletion in unordered array (ndeletion in ordered array (