2

I had a lecture on BigO notation, and I received a problem set to solve, but unfortunately we always get harder examples to solve that those presented(those which are presented are always some basic cases) during the lecture.

Here is the actual question: check if: $2^n = O(n^2) $

For sure it's false because $2^n$ grows much faster than $n^2$, but I have no idea how to show that.

Feng
  • 13,705
viGor
  • 21
  • My guess is that if your professor had used $2^n = O(n^2)$ as an example and instead assigned one of the examples that they used as homework, you would still complain that you are given harder examples to solve in homework than in class. – John Coleman Oct 26 '22 at 20:21

2 Answers2

3

Show that

$$\lim_{n\rightarrow\infty} Cn^2/2^n=0$$

for any $C$. Can be done with L'Hopital's rule in a straightforward fashion.

SimpleRick
  • 66
  • Is there any other way? I am currently on my first semester, and I should somehow show that with more basic methods, there is a rule in the university, that when you use something that wasn't shown on the lecture you may be asked to prove that it works :( – viGor Oct 26 '22 at 13:18
  • I mean there are multiple ways to go about this, such as choosing a threshold at which 2^n dominates Cn^2 for any C. However, L'Hopital's rule is traditionally introduced in the first two months of calculus 1. I would be astounded if they made you prove that. – SimpleRick Oct 26 '22 at 13:57
  • that's how it is at Polish universities... XD – viGor Oct 26 '22 at 17:51
1

Hints:

First, recall the gist and definition of big $O$ notation given by your syllabus. The gist is that we write $f(n)=O(g(n))$ if, as $n$ increases, $g$ grows faster than, or as fast as, $f$. It should be fairly clear which of $2^n$ and $n^2$ grows faster. The typical full definition is that for two real-valued functions of real variables $f$ and $g$, if all sufficiently large arguments $n>n_0$ have $|f(n)|$ equal to or bounded above by $Mg(n)$ for some positive real constant $M$, then we write that $f(n)=O(g(n))$.

So, in this case, we are asking whether it is possible to construct the bound $2^n\le Mn^2$ for all $n>n_0$ and some $M>0$.

Then, manipulate the inequality $2^n\le Mn^2$ with the aim of deriving a contradiction. One way to do this might be as $\displaystyle \frac{Mn^{2}}{2^{n}}-1\ge0$ and then expanding $2^n$ in order to compare it with polynomials.

Jam
  • 10,325