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 >= N

In the log3 vs log2 case its true that we have log3(x) < log2(x) for all big x. However, its also true that

          log2(x)
log3(x) = -------
          log2(3)

so we can choose some c larger than log2(3) to end up with

log2(x) < c * log3(x)

and thus log2(x) is O( log3(x) ).

---

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