Order of Growth and Asymptotic Notation Flashcards
what are the most commonly encountered orders of growth (in best to worst order)
constant logarithmic linear linear logarithmic quadratic cubic exponential
what does a linear logarithmic function look like
NlogN
what are the best orders of growth for large input sizes
constant
logarithmic
linear
linearlogarithmic
what does a constant run time mean
doesn’t change no matter what the input size is
example of a logarithmic run time algorithm
binary search
example of linear run time algorithm
for loop incs by constant amount each time
example of linear logarithmic algroithm
mergesort
example of quadratic or cubic order or growth run time algorithm
nested loops
example of exponential order of growth run time algroithm
combinational search
example of an algorithm with constant run time
statements and assignments
how does binary search work
array is sorted
low high and mid index
continuously divides in half based on if the middle index is greater or less than the number being searched for until the middle index is the number being searched for
can algorithms have more than one order of growth
yes, may change depending on input size
which order of growth of an algorithm is the most important
the asymptotic one
ie the one as the function tends to infinity
what are the three symbols used for describing asymptotic order or growth
Θ
O
Ω
Big theta shows what order or growth
the asymptotic order of growth
used to classify algorithms