Is it possible to prove big oh/big omega using graphs?

Question

I'm having a very, very hard time understand them. For example a question asking prove 42 is theta 1. Is it possible to use graphs?

Thanks for your time.

Answer 1

Geometric intuition, perhaps represented by a graph, can be useful. However, in this case it is perhaps not necessary. We have a function $f(n)$ given by $f(n)=42$ for all $n$. We have another function $g(n)$ given by $g(n)=1$ for all $n$. Boring functions, they are both constant.

I am not sure what your local definition of $\Theta$ is, the definitions can vary a little. We want to show that $f(n)$ is $\Theta(g(n))$. If you look at the definition, it means that there there is an $N$, and positive constants $k_1$ and $k_2$, such that if $n\gt N$ then $$k_1 g(n)\lt f(n)\lt k_2 g(n).$$ We can take $N=1$, it doesn't matter. Let $k_1=1$ and $k_2=50$.

Certainly $k_1 g(n)=g(n)=1\lt f(n)$. Also, $42=f(n)\lt 50=50g(n)$. So we are finished.

Informally we needed to show that $f(n)$ is (possibly only after a while) caught between a constant times $g(n)$ and another constant times $g(n)$.

Answer 2

If you look at this table, you can see you should only show there exist positive constants $k_1$ and $k_2$ such that $k_1\cdot1\leq 42 \leq k_2\cdot 1$.

For this particular case you can take $k_1=k_2=42$.

Not sure if using graphs is of any help in this case. In general it might be possible to use graphs to get intuition, but a formal proof would require a closer analysis of the growth rates of the functions involved.