Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order lower on this table will be big-O ones above it?
Here is the context of my question if it helps:
On
I'm not sure I fully understand your question, but have a look at (b): $$ \lim_{n \to \infty} \frac{\sqrt{n}}{n^{\frac{2}{3}}} = 0 $$ This means $f(n) = o(g(n))$, i.e. we can pick $c >0$ arbitrarily small, and $\forall c>0 \ \exists \ N(c)\ s.t. \ \forall n>N(c) \ \sqrt{n} < c n^{\frac{2}{3}}$. At the same time $\nexists N(s) \ s.t. \forall n>N(s) \ \sqrt{n} >s n^{\frac{2}{3}}$.Hence $f(n) \neq \Omega (g(n))$.
Here $f(n)$ is the numerator and $g(n)$ is the denominator.
On
is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other?
Yes, in the following sense.
Assume that $f(n)=h(n)+r(n)$ and $g(n)=k(n)+s(n)$ with $h(n)=\Theta(k(n))$, $r(n)=o(h(n))$ and $s(n)=o(h(n))$. Then indeed $f(n)=\Theta(g(n))$.
It is not true that all functions corresponding to the same entry in the table will be $\Theta$ of each other. In particular, $a^x = O(b^x)$ if and only if $|a| \leq |b|$. I'm not sure about the L-notation bit.
It is true, however, that $f = O(g)$ if $g$ is lower down on the table.