Transcription of The Growth of Functions and Big-O Notation
{{id}} {{{paragraph}}}
Example: dental hygienist
The Growth of Functions and Big-O Notation
The Growth of Functions and Big-O NotationBig-O NotationBig-O Notation allows us to describe the aymptotic Growth of a function without concern for i)constant multiplicative factors, and ii) lower-order additive terms. For example, using Big-O Notation ,the functionf(n) = 3n2+6n+7 is assumed to have the same kind of (quadratic) Growth asg(n) = do we choose to ignore constant factors and lower-order additive terms? One kind of functionthat we often consider throughout this course isT(n), which represents the worst-case number ofsteps required by a an algorithm to process an input of sizen. FunctionT(n) will vary dependingon the computing paradigm that is used to represent the algorithm. For example, one paradigmmight represent the algorithm as a C program, while another might represent it as a sequence ofrandom-access machine instructions.
( nk) for some positve k<1 sublinear growth ( n) linear growth ( nlogn) log-linear growth ( nlogkn), for some k 1 polylog-linear growth O(nk) for some k 1 polynomial growth (nk), for every k 1 superpolynomial growth (an) for some a>1 exponential growth Example 5. Use the above terminology to describe the growth of the functions from Examples 1 ...
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: