simplistic introduction to algorithmic complexity for simplicitywe will use random access machine as our model of computation in random access machinesteps are executed sequentiallyone at time step is an operation that takes fixed amount of timesuch as binding variable to an objectmaking comparisonexecuting an arithmetic operationor accessing an object in memory now that we have more abstract way to think about the meaning of timewe turn to the question of dependence on the value of the input we deal with that by moving away from expressing time complexity as single number and instead relating it to the sizes of the inputs this allows us to compare the efficiency of two algorithms by talking about how the running time of each grows with respect to the sizes of the inputs of coursethe actual running time of an algorithm depends not only upon the sizes of the inputs but also upon their values considerfor examplethe linear search algorithm implemented by def linearsearch(lx)for in lif =xreturn true return false suppose that is million elements long and consider the call linearsearch( if the first element in is linearsearch will return true almost immediately on the other handif is not in llinearsearch will have to examine all one million elements before returning false in generalthere are three broad cases to think aboutthe best-case running time is the running time of the algorithm when the inputs are as favorable as possible the best-case running time is the minimum running time over all the possible inputs of given size for linearsearchthe best-case running time is independent of the size of similarlythe worst-case running time is the maximum running time over all the possible inputs of given size for linearsearchthe worstcase running time is linear in the size of the list by analogy with the definitions of the best-case and worst-case running timethe average-case (also called expected-caserunning time is the average running time over all possible inputs of given size alternativelyif one has some priori information about the distribution of input values ( that of the time is in )one can take that into account people usually focus on the worst case all engineers share common article of faithmurphy' lawif something can go wrongit will go wrong the worst-case provides an upper bound on the running time this is critical in situations where there is time constraint on how long computation can take it is not more accurate model for today' computers might be parallel random access machine howeverthat adds considerable complexity to the algorithmic analysisand often doesn' make an important qualitative difference in the answer