Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O orders can be considered sets.
For example, $n^3 + 3n + 1$ can be considered an element of set $O(n^3)$. Moreover, $O(1)$ is a subset of $O(n)$ is a subset of $O(n^2)$, etc.
This got me thinking about big-Theta which is also obviously a set. What I found confusing is how each big-Theta order relates to each other. i.e. I believe that $\Theta(n^3)$ is not a subset of $\Theta(n^4)$. I played around with Desmos (graph visualiser) for a while and I failed to find how each big-Theta order relates to other orders. A simple example Big-Theta example graphs shows that although $f(n) = 2n$ is in $\Theta(n)$ and $g(n) = 2n^2$ is in $\Theta(n^2)$, the graphs in $\Theta(n)$ are obviously not in $\Theta(n^2)$. I kind of understand this visually, if I think about how different graphs and bounds might look like but I am having a hard time getting a solid explanation of why it is the way it is.
So, my questions are:
- Is what I wrote about big-O correct?
- How do big-Theta sets relate to each other, if they relate at all?
- Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.
- Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?