Recurrences
Asymptotic notation
\(O\)-notation(upper bounds)
\(O(g(n))=\){\(f(n)\): there exist constants \(c>0,n_0>0\) such that \(0≤f(m)≤cg(n)\) for all \(n>n_0\)}
\(\Omega\)-notation(lower bounds)
\(\Omega(g(n))=\){\(f(n):\) there exist constants \(c>0,n_0>0\) such that \(0≤cg(m)≤f(m)\) for all \(n>n_0\)}
\(\Theta\)-notation(tight bounds)
\(\Theta(g(n))=\Omega(g(n)) \cap O(g(n))\)
\(\omicron\)-notation
\(\omicron(g(n))=\){\(f(n)\): for any constants \(c>0\), there is a constant \(n_0>0\) such that \(0≤f(m)≤cg(n)\) for all \(n>n_0\)}
\(\omega\)-notation
\(\omega(g(n))=\){\(f(n)\): for any constants \(c>0\), there is a constant \(n_0>0\) such that \(0≤cg(m)≤f(m)\) for all \(n>n_0\)}