occasionallythe best-case performance of an algorithm is analyzed howeverthis is often of little interestbecause it does not represent typical behavior average-case performance often reflects typical behaviorwhile worst-case performance represents guarantee for performance on any possible input notice also thatalthough in this we analyze +codethese bounds are really bounds for the algorithms rather than programs programs are an implementation of the algorithm in particular programming languageand almost always the details of the programming language do not affect big-oh answer if program is running much more slowly than the algorithm analysis suggeststhere may be an implementation inefficiency this can occur in +when arrays are inadvertently copied in their entiretyinstead of passed with references another extremely subtle example of this is in the last two paragraphs of section thus in future we will analyze the algorithms rather than the programs generallythe quantity required is the worst-case timeunless otherwise specified one reason for this is that it provides bound for all inputincluding particularly bad inputwhich an average-case analysis does not provide the other reason is that average-case bounds are usually much more difficult to compute in some instancesthe definition of "averagecan affect the result (for instancewhat is average input for the following problem?as an examplein the next sectionwe shall consider the following problemmaximum subsequence sum problem  given (possibly negativeintegers an find the maximum value of = ak (for conveniencethe maximum subsequence sum is if all the integers are negative examplefor input - - - - the answer is ( through this problem is interesting mainly because there are so many algorithms to solve itand the performance of these algorithms varies drastically we will discuss four algorithms to solve this problem the running time on some computers (the exact computer is unimportantfor these algorithms is given in figure there are several important things worth noting in this table for small amount of inputthe algorithms all run in the blink of an eye so if only small amount of input is algorithm time input size , , , , , ( ( ( log ( na na na figure running times of several algorithms for maximum subsequence sum (in seconds