How can I solve $\mathcal{O}$-notations without using Java or any other programming language?
I only want to use pen and paper.
$\begingroup$
$\endgroup$
1
-
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$– jmiteJul 17, 2013 at 5:58
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
