if the element goes into splus (log )to delete sk and insert the new element if this is necessary thusthe total time is ( ( klog ko( log kthis algorithm also gives bound of ( log nfor finding the median in we will see how to solve this problem in (naverage time in we will see an elegantalbeit impracticalalgorithm to solve this problem in (nworst-case time event simulation in section we described an important queuing problem recall that we have systemsuch as bankwhere customers arrive and wait in line until one of tellers is available customer arrival is governed by probability distribution functionas is the service time (the amount of time to be served once teller is availablewe are interested in statistics such as how long on average customer has to wait or how long the line might be with certain probability distributions and values of kthese answers can be computed exactly howeveras gets largerthe analysis becomes considerably more difficultso it is appealing to use computer to simulate the operation of the bank in this waythe bank officers can determine how many tellers are needed to ensure reasonably smooth service simulation consists of processing events the two events here are (aa customer arriving and (ba customer departingthus freeing up teller we can use the probability functions to generate an input stream consisting of ordered pairs of arrival time and service time for each customersorted by arrival time we do not need to use the exact time of day ratherwe can use quantum unitwhich we will refer to as tick one way to do this simulation is to start simulation clock at zero ticks we then advance the clock one tick at timechecking to see if there is an event if there isthen we process the event(sand compile statistics when there are no customers left in the input stream and all the tellers are freethen the simulation is over the problem with this simulation strategy is that its running time does not depend on the number of customers or events (there are two events per customer)but instead depends on the number of tickswhich is not really part of the input to see why this is importantsuppose we changed the clock units to milliticks and multiplied all the times in the input by , the result would be that the simulation would take , times longerthe key to avoiding this problem is to advance the clock to the next event time at each stage this is conceptually easy to do at any pointthe next event that can occur is either (athe next customer in the input file arrives or (bone of the customers at teller leaves since all the times when the events will happen are availablewe just need to find the event that happens nearest in the future and process that event if the event is departureprocessing includes gathering statistics for the departing customer and checking the line (queueto see whether there is another customer waiting if sowe add that customerprocess whatever statistics are requiredcompute the time when that customer will leaveand add that departure to the set of events waiting to happen