1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 3 '14 at 17:32
  • $\begingroup$ cs.stackexchange.com/q/76361/755 $\endgroup$ – D.W. Jan 15 '18 at 18:38
  • $\begingroup$ Write down the definition of Big-Theta and it’s obvious. $\endgroup$ – gnasher729 Jan 29 at 7:30
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Aug 3 '14 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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