Efficiency Analysis

Notation

Big O ($O$)

It is defined as upper bound, is used to describe asymptotic upper bound. Mathematically, if f(n) describes the running time of an algorithm; $f(n)$ is $O(g(n))$ if there exist positive constant $C$ and $n_0$ such that, $0<=f(n)<=Cg(n)$ for all $n>=n_0$

Big Omega ($\Omega$)

It is define as lower bound and lower bound on an algorithm is the least amount of time required ( the most efficient way possible, in other words best case).
Just like O notation provide an asymptotic upper bound, Ω notation provides asymptotic lower bound.  **   Let f(n) define running time of an algorithm;
f(n) is said to be Ω(g (n)) if there exists positive constant C and (n0) such that $0<=Cg(n)<=f(n),\forall n>=n_0$

Big Theta ($\Theta$)

It is define as tightest bound and tightest bound is the best of all the worst case times that the algorithm can take.

Let f(n) define running time of an algorithm. 
f(n) is said to be Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n)). Mathematically, 

$$0<=f(n)<=C_{1}g(n)n>=n_0,0<=C_{2}g(n)<=f(n)n>=n_0$$

Merging both the equation, we get :  

$0<=C_{2}g(n)<=f(n)<=C_{1}g(n)\forall n>=n_0$ The equation simply means there exist positive constants C1 and C2 such that f(n) is sandwich between C2 g(n) and C1 g(n).

Master Theorem

$a,b$ is constant, $f(n)$ is additional function, $T(n)$ is a recursive function that $T(n)=aT(\frac{n}{b})+f(n)(a>0,b>1)$, then we have:

1. $T(n)=\Theta (n^{{\log }_b^a})$ when $f(n)=O(n^{{\log }_{b}a-ϵ}),ϵ>0$ (which is actually same as ${\log }_{b}a>f(n)$)
2. $T(n)=\Theta (n^{{\log }_{b}a}\log n)$ when $f(n)=\Theta (n^{{\log }_{b}a})$.
3. $T(n)=\Theta (f(n))$ when $f(n)=\Omega (n^{({\log }_{b}a)+epsilon},ϵ>0$ (which is actually same as ${\log }_{b}a<f(n)$), and have enough large $n$ and constant $c<1$ for $af(\frac{n}{b})\le cf(n)$
4. $T(n)=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$ when $f(n)=\Theta (n^{{\log }_{b}a}{\log }^k)$

Reference

重谈主定理（master定理）及其证明 - 这人太菜了 - 洛谷博客