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