1
$\begingroup$

I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve: $$\frac{\Theta(n)}{o(n)} =?$$ There are not many combinations and I was wondering if anyone could help me.

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to COMPUTER SCIENCE @SE. (Try $\Theta(n)$: $\Theta(n)$, $\omega(n)$, $\omega(n)$, ….) $\endgroup$
    – greybeard
    Jan 27, 2021 at 6:03

2 Answers 2

2
$\begingroup$

Classical resources: CLRS Introduction to Algorithms, 3d edition, pages 47, 1150, Donald Ervin Knuth TAOCP, 1997, volume 1, page 107.

More formal good resource for such cheatsheet you can find in Jeremy Avigad and Kevin Donnelly article.

And, at end, for non negative case, let me bring some well known properties:

$$ \begin{array}{l}O(f ) + O(g) = O(f + g) =O(\max(f,g))\\ C=Const. \Rightarrow C\cdot O(f) = O(C \cdot f) = O(f) \\ O(f ) O(g) = O(f g) \\ O( O( f)) = O(f ) \\ g \ne 0 \Rightarrow \frac{O(f)}{g} = O\left(\frac{f}{g}\right) \end{array} $$

For your case: $f \in \frac{\Theta(n)}{o(n)}$, if an only if $\lim\limits_{n \to \infty}f(n)=\infty$.

$\endgroup$
0
0
$\begingroup$

Let's do your example, $$ \frac{\Theta(n)}{o(n)}. $$ Since asymptotic notation doesn't care about constants, we can mentally replace $\Theta(n)$ by $n$. We are then left with $$ \frac{n}{f(n)}, \text{ where } \lim_{n\to\infty} \frac{f(n)}{n} = 0. $$ It follows that $$ \frac{\Theta(n)}{o(n)} = \omega(1). $$ A different way of expressing this is $$ \frac{\Theta(n)}{o(n)} \stackrel{(1)}= \frac{\Theta(1)}{o(1)} \stackrel{(2)}= \frac{1}{o(1)} \stackrel{(3)}= \omega(1). $$ Here (1) is reducing the fraction, (2) is hiding the constant, and (3) follows from the definitions.

Here is a third way. Let's substitute vague interpretations on both asymptotic notations: $$ \frac{\Theta(n)}{o(n)} = \frac{\sim n}{\mathop{\ll} n} \stackrel{(*)}= \mathop{\gg} 1 = \omega(1). $$ We're dividing something that scales like $n$ by something which is much smaller than $n$, so we get something big. We use the convention $\omega(1)$ to represent a function tending to infinity. There are similar interpretations for other asymptotic notations involving $1$. For example, $O(1)$ represents a quantity bounded from above.

I did all of these calculations without any cheat sheet. Instead, I know the definitions of $\Theta,O,o,\Omega,\omega$, and this is enough to "generate" whatever rules are needed on-the-fly. The other answer contains some useful rules which it is good to remember, but there is no need to separately consider all possible combinations of different types of asymptotic notation. Instead, it is crucial to remember the spirit of the definitions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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