๐Ÿ—๏ธ ฮ˜ฯฯตฮทฮ ฮฑฯ„ฯ€๐Ÿšง (under construction)

Absolutely Dominated
Let f,g:N0โ†’Rโ‰ฅ0, we say that g is absolutely dominated by f iff for all nโˆˆN0,g(n)โ‰คf(n)
Squared Dominates Linear
Let f(n)=n2 and g(n)=n show that g is absolutely dominated by f
Absolutely Dominated up to a Constant Factor
Let f,g:N0โ†’Rโ‰ฅ0, we say that g is absolutely dominated up to a constant factor by f iff there exists cโˆˆR+ such that g is absolutely dominated by cf
Eventually Dominated
Let f,g:N0โ†’Rโ‰ฅ0, we say that g is eventually dominated by f iff there exists some n0โˆˆR+ such that โˆ€nโˆˆN+,nโ‰ฅn0 then we know g(n)โ‰คf(n)
Lower Degree Polynomial plus Constant is Eventually Dominated by Higher Degree
Let f(n)=n2 and g(n)=n+90
Eventually Dominated up to a Constant Factor
Let f,g:N0โ†’Rโ‰ฅ0, we say that g is eventually dominated by f iff there exists some cโˆˆR+ such that g is eventually dominated by cf
Big-O
Suppose we have f:โ„•0โ†’โ„โ‰ฅ0, then we define the set O(f) as all functions that are eventually dominated up to a constant factor by f
Big-O of
Let f,g:N0โ†’Rโ‰ฅ0, we say that g is big-o of f iff gโˆˆO(f)

Note that if g is big-o of f, then we know that f is an asymptotic upper bound for g

Basic Polynomial
Suppose f(n)=n3 and g(n)=n3+100n+5000, show that gโˆˆ๐’ช(f)
Omega
Suppose we have f:โ„•0โ†’โ„โ‰ฅ0, then we define the set ฮฉ(f) as the set of all functions g:โ„•0โ†’โ„โ‰ฅ0 such that โˆƒc,n0โˆˆR+ย s.t.ย โˆ€nโˆˆN0,nโ‰ฅn0โŸนg(n)โ‰ฅcยทf(n)
Omega of
Let f,g:N0โ†’Rโ‰ฅ0, we say that g is omega of f iff gโˆˆฮฉ(f)

Here we can think of ฮฉ as being O's counter part, so that when g is omega of f, then f is a lower bound on g's eventual growth rate.

Theta
Suppose we have f:โ„•0โ†’โ„โ‰ฅ0, then we define the set ฮ˜(f) as the set of all functions g:โ„•0โ†’โ„โ‰ฅ0 such that gโˆˆO(f)โˆฉฮฉ(f) where we are using big-o and theta

The point of theta is to say that g is both eventually upper and lower bounded by f which means that g should grow asymptotically the same as f