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

I only want to use pen and paper.


2 Answers 2


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.

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

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

Link : https://stackoverflow.com/questions/5791146/big-o-big-oh-notation-problem

If you don't understand it, edit your question appropriately so we can better help you.


Not the answer you're looking for? Browse other questions tagged or ask your own question.