# Why are different logarithms in the same Θ even thought their difference diverges?

As I have read in book and also my prof taught me about the asymptotic notations

The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large value of $n$.

So from here my confusion is-

$2^n=O(3^n)$ and $\log_2 n=\Theta(\log_3 n)$

First relation is clear to me and second relation is confusing me.Though I derived $\log_2 n$ and $\log_3 n$ to same base and noticed that $\log_2 n=\log_{10} n/\log_{10} 2$ and $\log_3 n=\log_{10}n/\log_{10}3$. So In both constant factor can be removed. So second relation is also OK.

Still there remain a doubt that when I see the graph plot of $\log_2 n$ and $\log_3 n$, $\log_2 n$ is always above $\log_3 n$ and grows faster than $log_3 n$ i.e the difference of log values increases as n increases. Then I got more confused when I saw the graph plot of $x_1=y$ and $x_2=2y$ in which again $x_2$ is above $x_1$ and difference is increasing b/w them as $y$ increases.

So now I want to know .How do I distinguish from graph about the asymptotic relations of the function. In what sense they say one function is upper bounded by the other though 2 lines with different slopes also following this.Why don't we say one line is upper bounded by the other.We only say they are related by $\Theta$.

• You may profit from reading our reference questions and the posts linked from there. Then, understand that absolute errors can diverge; such is hidden by Landau symbols. – Raphael Aug 3 '14 at 17:32
• cs.stackexchange.com/q/76361/755 – D.W. Jan 15 '18 at 18:38
• Write down the definition of Big-Theta and it’s obvious. – gnasher729 Jan 29 '20 at 7:30

You are missing one thing in your definition of asymptotic notation. In addition to only caring about large values of N, we also ignore constant multiplicative factors.

$$f$$ is $$O(g)$$ if there exists a large $$N$$ and a constant $$c$$ such that $$f(x) < c g(x)$$ for all $$x \ge N$$

In the $$\log_3$$ vs $$\log_2$$ case its true that we have $$\log_3 x < \log_2 x$$ for all big $$x$$. However, its also true that

$$\begin{equation*} \log_2 x = \frac{\log_3 x}{\log_2 3} \end{equation*}$$

so we can choose some $$c$$ larger than $$\log_2 3$$ to end up with:

$$\begin{equation*} \log_2 x < c \cdot \log_3 x \end{equation*}$$

and thus $$\log_2 x$$ is $$O(\log_3 x)$$.

The same reasoning does not apply to $$2^n$$ and $$3^n$$. There is no constant multiplicative factor that will make the $$2^n$$ catch up to $$3^n$$ for all big $$n$$.

• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Aug 3 '14 at 17:33