This section goes into how to specifically talk about run-times. For instance, it discusses disregarding constant factors and terms not of the highest order coefficient. In building up this description, the concepts of Asymptotic upper and lower bounds are introduced to help fully categorize running times. O(*) deals with upper bounds as opposed to specific growth rates. Capital omega is used similar to O(*) to discuss the lower bound. Lastly, asymptotic tight bounds are introduced and are represented by a capital theta. The remainder of the section details specific growth rates of the different bounds and the associated proofs behind them.

This section, once again, did not merely detail a long-winded algorithm. As such, it gets a 7/10.

courses/cs211/winter2018/journals/goldm/ch2.2.txt · Last modified: by goldm
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0