# How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language?

I only want to use pen and paper.

• There is no method which will always find an answer. It's an undecidable problem. There are, however, general techniques. See here: cs.stackexchange.com/questions/12899/… – jmite Jul 17 '13 at 5:58

I assume that you want to solve the following problem:

Given two functions $$f(n)$$ and $$g(n)$$, with, let's say, $$g, f: \mathbb{N} \to \mathbb{R}$$.

Question: Is $$f(n) \in \mathcal{O}(g(n))$$?

You can recall the definition of the $$\mathcal{O}$$-notation from e.g. Wikipedia, which tells you that

$$f(n) \in \mathcal{O}(g(n)) \quad\text{if and only if}\quad\exists n_0 \in \mathbb{N}, c \in \mathbb{R}: f(n) \le c\cdot g(n) \text{ for all } n \ge n_0.$$

This reduces the given problem to a merely analytical one. You have to develop some intuition here whether or not the answer to your question will be "yes" or "no".

If you think that $$f(n) \in \mathcal{O}(g(n))$$, then you can show this by starting from $$f(n)$$ and formulate inequalities of the form $$f(n) \le ... \le c\cdot g(n)$$ which may potentially only hold for sufficiently large numbers. The maximum of those "sufficiently large numbers" then will be your $$n_0$$.

In order to show the contrary, i.e. $$f(n) \not\in \mathcal{O}(g(n))$$, you would have to show that there are no such $$n_0$$ and $$c$$, which is considerably harder. Probably, you will prove that $$\limsup_{n \to \infty} \frac{f(n)}{g(n)}$$ does not exist.

• While strictly true, it's finding $f(n)$ that's usually the hard/interesting part. – jmite Jul 17 '13 at 15:45
• Very nice answer. Does it really have to be limsup or just ordinary limit? – darxsys Jul 19 '13 at 4:13

Follow this really good example. There is no Big-O using any programming languages.