-2
$\begingroup$

This question already has an answer here:

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

I only want to use pen and paper.

$\endgroup$

marked as duplicate by jmite, A.Schulz, Luke Mathieson, Kaveh, Juho Jul 17 '13 at 9:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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/… $\endgroup$ – jmite Jul 17 '13 at 5:58
3
$\begingroup$

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.

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

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.

$\endgroup$

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