« previous | Friday, August 31, 2012 | next »
Time Complexity
We want to asymptotically count the number of operations independent of compilers and optimization settings.
Sad notation:
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = O(g) \longrightarrow f \in O(g)}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(f) = O(g) \longrightarrow O(f) \subseteq O(g)}
Big-Oh
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g:\mathbb{N}\to\mathbb{C}}
be a function.
Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(g)}
is the set of functions:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(g) = \left\{ f:\mathbb{N}\to\mathbb{C} \mid \exists u > 0 \ \exists n_0 \in \mathbb{N} \ \forall n \ge n_0 \ \left| f(n) \right| \le u \, \left| g(n) \right| \right \}}
Little-Oh
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(g) = \left\{ f:\mathbb{N}\to\mathbb{C} ~\bigg|~ \lim_{n\to\infty} \frac{\left|f(n)\right|}{\left|g(n)\right|} = 0 \right\}}
It follows that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle o(f) \subseteq O(f)}
Big-Ω
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Omega(g) = \left\{ f:\mathbb{N}\to\mathbb{C} \mid \exists d > 0 \ \exists n_0 \in \mathbb{N} \ \forall n \ge n_0 \ d \, \left| g(n) \right| \le \left| f(n) \right| \right \}}
Big-Θ
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(g) = \left\{ f:\mathbb{N}\to\mathbb{C} \mid \exists u,d > 0 \ \exists n_0 \in \mathbb{N} \ \forall n \ge n_0 \ d \, \left| g(n) \right| \le \left| f(n) \right| \le u \, \left| g(n) \right| \right \}}
Corrected Proof of Sorting Lower Bound
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 2^h &\ge n! \\ \log_2{2^h} & \ge \log_2(n!) = \log_2(n(n-1)\dots(2)(1)) \\ h &\ge \log_2(n!) \ge \log_2\left(\left(\frac{n}{2}\right)^\frac{n}{2}\right) \\ h &\ge \frac{n}{2} \log_2\left(\frac{n}{2}\right) = \frac{n}{2} \log_2{n} - \frac{n}{2} \log_2{2} \\ h &\in \Omega(n \log{n}) \end{align}}