Analysis of Algorithms - Big O Notation Equivalences - Limits

Question

Please see below block question from review for test.

True Or False? Justify Your answers

A) is 2^(n+1) = O($2^n$)

B) is 2^2n = O($2^n$)

C) is log($n^2$) = O(logn)

D) is log($2^n$) = O(log(n))

I am not too good in discrete and definately worse at calculus, and when applying the following formula

Given functions f(n), g(n), f(n) = O(g(n)) if $\lim\limits_{n \to infinite} \frac{f(n)}{g(n)}$ = L where L ∈ (0,infinite)

I get the answer "True" for each, as the f(n) function has higher growth rate, in every scenario, the limit will always = infite.

Is this correct? Am i Solving these properly

PArt of the question says "Justify your answer" the Limit is the justification.

Answer 1

First, the correct version of the theorem you cite is

Given functions $f,g \colon \mathbf N \to \mathbf R$, then $f = O(g)$ iff $\limsup_{n\to\infty} \left|\frac{f(n)}{g(n)}\right| < \infty$.

Second, the limit is not always infinite in your cases, we have \begin{align*} \frac{2^{n+1}}{2^n} &= 2 < \infty\\ \frac{2^{2n}}{2^n} &= 2^n\\ &\to \infty.\\ \frac{\log(n^2)}{\log n} &= \frac{2\log n}{\log n}\\ &= 2 < \infty.\\ \frac{\log(2^n)}{\log n} &= \frac{n\log 2}{\log n}\\ &\to \infty. \end{align*}

Answer 2

The "Big $\text{O}$ notation" means that if $f(n) = \text{O}g(n)$ then there is some constant $C$ such that for all sufficiently large $n$, $$ |f(n)| \leq C|g(n)|$$

So for example, you are right about (a) because $2^{n+1} = 2 \cdot 2^n$ so if we take $C$ as any number $C \geq 2$ the definition is satisfied; the "justification" would be to note that $2^{n+1} = 2 \cdot 2^n$.

For (b), though, the answer is false: $2^{n+1} = 2^n \cdot 2^n$ and there is no $C$ that for sufficiently large $n$ is greater than $2^n$.

(c) is true, the justification is that $$\log(n^2) = 2 \log(n)$$

(d) is false. $\log(2^n) = n \log(2) = \text{O}(n)$