Does the base component affect Logarithmic and Exponential Runtimes in Time Complexity (Big-Oh) of an algorithm?

Question

Let us look at the following 2 cases:

1. We say a binary search implementation in a sorted array of size n has a time complexity of $O(\log n)$. In detail, $O(\log_{2} n)$ because binary search halves the input space with each iteration.

2. In a recursive code block as below, We say that the time complexity is $O(3^n)$ as there will be exponential growth of branches in the order of 3 per iteration.

    int recursive(int n){
    if (n<=1){
      return 1;
     }
    else{
      return recursive(n-1) + recursive(n-2) + recursive(n-3);
     }
    }

Since Time Complexity talks about the behavior/trends of algorithms with respect to input size,

Can we say that the base component in the above cases is not crucial?

(logarithm's base component is 2 & exponential's base component is 3)

i.e., Can we just say their Time Complexity as $O(\log_{k} n)$ and $O(k^n)$ where $k$ is a constant?

Answer 1

The basis of logarithm and the basis of an exponential are very different.

By logarithm basis change formula we have: $$\log_a n=\frac{\log_c n}{\log_c a} \, $$ where $\log_c a$ is a constant (independent on $n$). Thus $O(\log_a n)=O(\log_c n)$.

For exponentials it is not the case:

$$4^n=(2\cdot 2)^n=2^n \cdot 2^n = (2^n)^2 \ . $$

So, a multiplicative factor at the basis of the exponential becomes a power-factor. If you call $2^n=y$, we have $O(4^n)=O(y^2)$ which is a polynomial in $y$ with a larger degree than $O(2^n)=O(y)$.

In conclusion, you can just omit the basis of the logarithm in big-O notation, but you can't do it with exponentials

Answer 2

The logarithms in different bases are proportional to each other, and in complexity analysis a constant factor is unimportant. Hence

$$O(\log_a(n))=O\left(\frac{\log(n)}{\log(a)}\right)=O(\log(n)).$$

But such a rule does not hold for exponentials, there is no constant such that

$$a^n=c\,e^n.$$

---

Proof:

Taking the natural logarithm,

$$n\ln(a)=\ln(c)+n$$ makes

$$n=\frac{\ln(c)}{\ln(a)-1},$$ which is absurd.

---

Numerical insight:

$$\frac{\log_2(4)}{\log_4(4)}=\frac21=2,\\\frac{\log_2(16)}{\log_4(16)}=\frac42=2,\\\frac{\log_2(64)}{\log_4(64)}=\frac63=2,\\\cdots$$

while

$$\frac{4^1}{2^1}=\frac42=2,\\\frac{4^2}{2^2}=\frac{16}4=4,\\\frac{4^3}{2^3}=\frac{64}8=8,\\\cdots$$