1
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ I am not sure that I get your point. Does this mean they are unequal in both cases? $\endgroup$
    – Bashyar
    Oct 29, 2020 at 14:05
  • $\begingroup$ @Bashyar The classes coincide for constant $t$. They do not coincide, in general, if $t$ is not a constant. $\endgroup$
    – Steven
    Oct 29, 2020 at 14:28
  • $\begingroup$ I come later and confirm Steven's comment. $\endgroup$
    – zkutch
    Oct 29, 2020 at 16:20
  • $\begingroup$ @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? $\endgroup$
    – Bashyar
    Oct 29, 2020 at 16:41
  • $\begingroup$ @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. $\endgroup$ Nov 10, 2020 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.