# Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?

Example: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $$O(\log_t n)$$ (where $$t \in \mathbb{N}$$ is the order of the tree).

There was one true/false question on exam which asks if the Big-O complexity of the operation mentioned in the example above is $$O(\log_2 n)$$.

I am beginner in this topic but I understand that both $$O(\log_2 n)$$ and $$O(\log_t n)$$ belong to the same Big-O complexity category of $$O(\log n)$$. The only thing which confuses me is whether it matters if the base of a logarithm is given as a constant or as a variable.

Additionally: Would the answer change if we swap the bases from the example and the question?

Edit (if relevant): The mentioned complexity is related to the number of disk accesses and it is not the time complexity.

• Do you know that $\log_b(n) = \ln(n) / \ln(b)$? Oct 29, 2020 at 12:05
• Yes, I do know that. Oct 29, 2020 at 12:21
• (I don't want to think about $O(\log_n n)$.) Oct 29, 2020 at 13:18
• Hmm. You do know, I trust, that $log_nn=1$ wherever it's defined. Oct 29, 2020 at 14:37

Let's look at the root of question: we have $$\log_2 n=\frac{\ln n}{\ln 2}$$ and $$\log_t n=\frac{\ln n}{\ln t}$$, so $$\log_2 n = \frac{\ln t}{\ln 2} \log_t n$$ and when $$t$$ is constant, then logarithms are in same complexity class.
Bit if $$t=t(n)$$, then we can ruin this relation and create any class $$O(f(n))$$ of complexity taking $$t(n)=e^{\frac{\ln n}{f(n)}}$$ we have $$\log_t n=\frac{\ln n}{\ln t}=f(n)$$.
• @Bashyar The classes coincide for constant $t$. They do not coincide, in general, if $t$ is not a constant. Oct 29, 2020 at 14:28
• @Steven Thanks for the comment. This makes things much clearer to me. In the meantime I have also asked my professor and from his answer I could conclude the same. The source of my confusion was that I thought that $t$ is a variable, when in fact it is a constant. This opens a new question for me: How to tell difference between a constant and a variable? Oct 29, 2020 at 16:41
• @Bashyar in the context of data structures, if a parameter doesn't change through the life-time of the data structure, then it is a constant. For example, changing $t$ requires you to rebuild the B-Tree from scratch. On the other hand, insert/delete operations causes some parameters (like number of nodes and depth of the tree) to vary — these are variables. Nov 10, 2020 at 6:25