Knowing the dominance relation between common functions is important because we want algorithms whose time complexity is as low as possible in the hierarchy. A logarithm is simply an inverse exponential function. Saying is equivalent to saying that . Exponential functions, like the amount owed on a n year mortgage at an interest rate of per year, are functions which grow distressingly fast, as anyone who has tried to pay off a mortgage knows. Thus inverse exponential functions, ie.
Binary search is an example of an algorithm.
After each comparison, we can throw away half the possible number of keys. If you have an algorithm which runs in time, take it, because this is blindingly fast even on very large instances. Listen To Part 2-8 Properties of Logarithms Recall the definition, . Any exponential dominates every polynomial. This is why we will seek to avoid exponential time algorithms.