Functions in Asymptotic Notation

When we use asymptotic notation to express the rate of growth of an algorithm's running time in terms of the input size $n$, it's good to bear a few things in mind.

Let's start with something easy. Suppose that an algorithm took a constant amount of time, regardless of the input size. For example, if you were given an array that is already sorted into increasing order and you had to find the minimum element, it would take constant time, since the minimum element must be at index $0$. Since we like to use a function of $n$ in asymptotic notation, you could say that this algorithm runs in $\Theta(n^0)$ time. Why? Because $n^0 = 1$, and the algorithm's running time is within some constant factor of $1$. In practice, we don't write $\Theta(n^0)$, however; we write $\Theta(1)$.

Now suppose an algorithm took $\Theta(\log_{10}n)$ time. You could also say that it took $\Theta(\lg{n})$ time (that is, $\Theta(\log_2n)$ time. Whenever the base of the logarithm is a constant, it doesn't matter what base we use in asymptotic notation. Why not? Because there's a mathematical formula that says