algorithm analysis /*linear-time maximum contiguous subsequence sum algorithm *int maxsubsum const vector int maxsum thissum forint size)++ thissum +aj ]ifthissum maxsum maxsum thissumelse ifthissum thissum return maxsumfigure algorithm than the sketch aboveare almost always requiredeven thenmany people still are not convinced alsomany of these algorithms require trickier programmingleading to longer development but when these algorithms workthey run quicklyand we can test much of the code logic by comparing it with an inefficient (but easily implementedbrute-force algorithm using small input sizes an extra advantage of this algorithm is that it makes only one pass through the dataand once [iis read and processedit does not need to be remembered thusif the array is on disk or is being transmitted over the internetit can be read sequentiallyand there is no need to store any part of it in main memory furthermoreat any point in timethe algorithm can correctly give an answer to the subsequence problem for the data it has already read (the other algorithms do not share this propertyalgorithms that can do this are called online algorithms an online algorithm that requires only constant space and runs in linear time is just about as good as possible logarithms in the running time the most confusing aspect of analyzing algorithms probably centers around the logarithm we have already seen that some divide-and-conquer algorithms will run in ( log ntime besides divide-and-conquer algorithmsthe most frequent appearance of logarithms centers around the following general rulean algorithm is (log nif it takes constant ( ( )time to cut the problem size by fraction (which is usually on the other handif constant time is required to merely reduce the problem by constant amount (such as to make the problem smaller by )then the algorithm is (