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

Question

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

Please help me understand this concept.

Answer 1

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