Need help understanding this proof (algorithm complexity)

28 Views Asked by At

enter image description here

I don't understand how it's valid to present this counterexample. It doesn't satisfy $f(n) = O(g(n))$ since $f(n)$ is not $O(g(n))$. $f(n) = \omega (2^n)$ if $f(n)$ is $2n$ and $g(n)$ is $n$.

So how is it valid to simply "Let $f(n) = 2n$ and $g(n)=n.$"?

1

There are 1 best solutions below

0
On

Setting $f(n) = 2n$ and $g(n) = n$, the hypothesis is satisfied that $f(n) \in O(g(n) )\Leftrightarrow 2n \in O(n)$ since big O doesn't care about constant factors.

However when you replace each side by $2^{f(n)}$ and $2^{g(n)}$ respectively, you get the claim that $ 2^{f(n)} \in O(2^{g(n)}) \Leftrightarrow 4^n \in O(2^n)$

But this claim is false, since $4^n$ grows faster than $2^n$ in the sense that $\lim_{n\rightarrow \infty} 4^n / 2^n = \infty$

So since the hypothesis is satisfied, but the conclusion is not, it is a counter-example.