Logarithms

We review some properties of logarithms and then see why it could be useful in CSE 331.

  1. This can be proved by induction and is left as an exercise.

  2. If we do not specify the base of a logarithm, it is always to base 2.

Definition

We begin with the definition of logarithm:

Logarithm

We call a number $b$ to be $\log_a{c}$ (where $a,c\gt 0$) if and only if \[a^b=c.\]

In this note, we briefly present some properties of logarithms. For a more comprehensive tutorial on logarithms (and their properties), take a look at this Khan Academy Tutorial .

The first implication

We now consider one implication of logarithms, which will be used a few times in CSE 331:

Lemma 1

Let $n\ge 1$ be an integer and let $x\ge 0$ be the smallest integer such that \[\frac{n}{2^x} \lt 1.\] Then $x=\left\lceil \log_2{(n+1)}\right\rceil$. In particular, $x$ is $O(\log_2{n})$.

Proof Idea

We will use the definition of $\log_2{n}$ and the fact that $2^x$ is increasing in $x$.

Proof Details

By definition we have \[2^{\log_2{n}} = n.\] Further, as $2^x$ is increasing in $x\ge 0$ (this can be shown e.g. by noting that the derivative of $2^x$ is positive for $x\ge 0$), we have that for any $x\ge \log_2(n+1)$, we have \[2^x > n \text{ or equivalently } \frac{n}{2^x} < 1.\] The proof is complete by noting that $\left\lceil \log_2(n+1)\right\rceil$ is the smallest integer greater than or equal to $\log_2(n+1)$.

But why should I care?

It turns out that Lemma 1 is useful in proving asymptotic bound in runtime analysis. For example consider the well-known binary search algorithm:

Binary Search

                                        //Input: A[0],...,A[n-1];v (A is sorted)

					left=0;
					right=n-1;

					while(left <= right)
					{
						mid=ceil( (right+left)/2);
						if(A[mid]==v)
							return mid; // v is present 
						else if(A[mid]< v)
							left=mid+1; // Search for v in right half
						else
							right = mid-1; // Search for v in left half
					}

					return -1; // v is not present

It turns out that Lemma 1 is crucial in proving the following well known bound on runtime of binary search: i

Theorem

Binary search runs in time $O(\log_2{n})$.

Proof Idea

The runtime of binary search is dominated by the number of iterations of the while loop in line 6. We bound the latter by $O(\log_2{n})$ with the help of Lemma 1 (by observing that the quantity right-left decreases by at least a half in each iteration).

Proof Details

We first note that all steps outside of the while loop take $O(1)$ time. Further, each iteration also takes $O(1)$ time (since each step in the iteration are basic operations such as comparison, assignment and simple arithmetic operations). Thus, if we can argue that while loop runs $O(\log_2{n})$ times, we would be done.

To bound the number of iterations of the while loop, let $\ell_i$ and $r_i$ denote the value of left and right at the start of the $i$th iteration. Further, we keep track of $p_i=r_i-\ell_i$. Note that $p_0=n-1$ and for the smallest integer $x$ such that $p_x\lt 1$, the algorithm will terminate at the end of the $x$th iteration. This is because at the start of this round left<=right but then if line 10 is not executed then either line 13 or 15 will ensure that at the start of the next iteration left> right and hence the algorithm will stop. (Note that if line 10 is executed then the algorithm will also terminate.)

Finally we argue that $x=O(\log_2{n})$. Towards this end consider the $i$th iteration for some $i\le \left\lceil \log_2{n}\right\rceil$. Then either line 10 is executed (in which case the algorithm terminates and we are done) otherwise either line 13 or 15 are executed. In the latter case we claim that \[p_{i+1}\le \frac{p_i}{2}.\] To see this note that if line 13 is executed then $r_{i+1}=r_i$ and $\ell_{i+1} \ge \frac{\ell_i+r_i}{2}+1$ and if line 15 is executed then $\ell_{i+1}=\ell_i$ and $r_{i+1}\le \frac{\ell_i+r_i}{2}$. It can then be verified that in both cases $p_{i+1}\le p_i/2$. Finally, we note that this implies1 that \[p_i\le \frac{p_0}{2^i}=\frac{n-1}{2^i}.\] Lemma 1 and the observation above that $p_x\lt 1$ then implies $x=O(\log_2{n})$, as desired.

The base change formula

The following well-known result also turns out to be useful:

Base Change Lemma

For $a,b,c\gt 0$, we have \[\log_b{a}=\frac{\log_c{a}}{\log_c{b}}.\]

See e.g. this Khan academy video for a proof:

The base change lemma implies the following result (which is left as an exercise):

Exercise 1

Argue that for any constant base $b$, $\log_b{n}=O(\log_2{n})$.

The above allows us to use the following convention in CSE 331 (which guys have followed so far in say CSE 250 too):

Convention

Since for all constant $b$, $O(\log_b{n})$ is $O(\log_2{n})$, we will denote $O(\log_b{n})$ for any constant $b$ by $O(\log{n})$, i.e. we will not explicitly state the base since asymptotically they are all the same.

But why so we need another base?

It turns out that sometimes we do need to consider logarithms to bases other than $2$. For example consider the following variant of the binary search algorithm, where c is a constant strictly greater than 1:

Modified Binary Search

                                        //Input: A[0],...,A[n-1];v (A is sorted)

                                        left=0;
                                        right=n-1;

                                        while(left <= right)
                                        {
                                                mid=ceil( (right+left)/c); // Note that c has replaced 2
                                                if(A[mid]==v)
                                                        return mid; 
                                                else if(A[mid]< v)
                                                        left=mid+1; 
                                                else
                                                        right = mid-1; 
                                        }

                                        return -1; // v is not present

It turns out that using $c$ to define the mid instead of $2$ does not change the asymptotic runtime:

Exercise 2

Prove that the modified binary search runs in $O(\log{n})$ time.

Hint: Modify the arguments for the Theorem, Lemma 1 and use Exercise 2.

Another use of logarithms

One can also use logarithms to compare running times. Towards this end, the following simple observation is useful:

Lemma 3

For any $a,b\gt 0$, we have \[ a = b^{\log_b{a}}.\]

We illustrate the usefulness of Lemma 3 with an example.

Which runtime is better?

Say I tell you there are two algorithms that solve the same problem but on inputs of size $n$, one runs in time $T_1(n)=n^{\log{n}}$ while the other runs in time $T_2(n)=\left(\log{n}\right)^n$. Which one should you choose?2

Before we proceed to answer the problem, above we state another property of logarithms that is useful:

Lemma 4

For any $a,b,c\ge 0$, we have \[\log_b\left(a^c\right) =c\cdot \log_b{a}.\]

See e.g. this Khan academy video for a proof:

Now let us return to our problem. One might think that since the base $n$ is larger than the base $\log{n}$, $T_1(n)$ grows faster than $T_2(n)$. And one would be wrong. To see this, use Lemmas 3 and 4 and note that \[T_1(n) = 2^{\log^2{n}}\text{ and } T_2(n)= 2^{n\log\log{n}}.\] Since $\log^2{n}\lt n\log\log{n}$ for all integers $n\gt 4$, we have that $T_1(n)$ is $O(T_2(n))$ and hence, one should pick the first algorithm since it is (asymptotically) faster.