So in a future assignment, I noticed some problems that requested us to just "use" these rules. I was wondering if any rules existed for little-theta, and little-omega as well (using limit as x approaches infinity of f(x)/g(x)).
Also, are there any formal proofs of these rules? I've managed to write proofs for several of them (Big-O, little-theta, little-omega). But I'm having trouble with the others -- namely at the moment, Big-Omega. I'm using a limit ratio, and then translating that using the definition of a formal limit, and then applying the definition of the asymptotic notation in question.
So I saw this post: https://math.stackexchange.com/questions/925053/using-limits-to-determine-big-o-big-omega-and-big-theta
http://aofa.cs.princeton.edu/lectures/lectures13/AA01-AofA.pdf
Definitions which do not involve limits are provided here:
Big O
f = O(g) iff there exists n0, c > 0 such that for all n >= n0, f(n) < c*g(n).
Big Omega
f = Omega(g) iff g = O(f).
Big Theta
f = Theta(g) iff f = O(g) and f = Omega(g).
Little o
f = o(g) iff for all c > 0 there exists n0 such that for n >= n0, f(n) < c*g(n)
Little omega
f = omega(g) iff g = o(f)
There is no "little theta". You might also find "Little o" and "Little omega" defined as "O \ Theta" and "Omega \ Theta"; these definitions can be proved equivalent by showing the sets they describe are equal (i.e., o is a subset of O \ Theta, and O \ Theta is a subset of o).