Skip to main content
added 11 characters in body
Source Link
vonbrand
  • 14.1k
  • 3
  • 41
  • 52

That really makes no sense. Check out e.g. Hildebrand's "Asymptotic analysis""Short course on Asymptotics" for details of the meanings and usage of asymptotic notations.

In a nutshell, for typical CS use: $O(f(n))$ is some function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n_0$ for some (again unspecified) constant $n_0$. The functions $f$ and $g$ are positive in our usage. It is meant to represent some rough upper bound, in the sense that an "equation" like:

$\begin{equation*} e^{1/n} = 1 + O(1/n) \end{equation*}$

means that $e^{1/n}$ is $1 + g(n)$ (here, by the series for $e^x$ it is $g(n) = \sum_{k \ge 1} \frac{1}{k! n^k}$) and $g(n) = O(1/n)$ (the sum of the terms after the first is smaller than a constant times $1/n$, as you can check), and $g(n) = O(1/n)$. The convention is that the right hand side is a rougher expression of the left hand side, "$=$" here is not equality. For example, you can check that:

$\begin{align*} 3 \sqrt{n} &= O(n^3) \\ 17 n^3 &= O(n^3) \end{align*}$

but that doesn't mean $\sqrt{n} = 17 n^3$. If you use $O(\cdot)$ on the left hand side, make sure the right hand side is rougher. And "$<$" makes no sense whatsoever, any such inequality is subsumed by the $O(\cdot)$ itself.

That really makes no sense. Check out e.g. Hildebrand's "Asymptotic analysis" for details of the meanings and usage of asymptotic notations.

In a nutshell, for typical CS use: $O(f(n))$ is some function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n_0$ for some (again unspecified) constant $n_0$. The functions $f$ and $g$ are positive in our usage. It is meant to represent some rough upper bound, in the sense that an "equation" like:

$\begin{equation*} e^{1/n} = 1 + O(1/n) \end{equation*}$

means that $e^{1/n}$ is $1 + g(n)$ (here, by the series for $e^x$ it is $g(n) = \sum_{k \ge 1} \frac{1}{k! n^k}$) and $g(n) = O(1/n)$ (the sum of the terms after the first is smaller than a constant times $1/n$, as you can check), and $g(n) = O(1/n)$. The convention is that the right hand side is a rougher expression of the left hand side, "$=$" here is not equality. For example, you can check that:

$\begin{align*} 3 \sqrt{n} &= O(n^3) \\ 17 n^3 &= O(n^3) \end{align*}$

but that doesn't mean $\sqrt{n} = 17 n^3$. If you use $O(\cdot)$ on the left hand side, make sure the right hand side is rougher. And "$<$" makes no sense whatsoever, any such inequality is subsumed by the $O(\cdot)$ itself.

That really makes no sense. Check out e.g. Hildebrand's "Short course on Asymptotics" for details of the meanings and usage of asymptotic notations.

In a nutshell, for typical CS use: $O(f(n))$ is some function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n_0$ for some (again unspecified) constant $n_0$. The functions $f$ and $g$ are positive in our usage. It is meant to represent some rough upper bound, in the sense that an "equation" like:

$\begin{equation*} e^{1/n} = 1 + O(1/n) \end{equation*}$

means that $e^{1/n}$ is $1 + g(n)$ (here, by the series for $e^x$ it is $g(n) = \sum_{k \ge 1} \frac{1}{k! n^k}$) and $g(n) = O(1/n)$ (the sum of the terms after the first is smaller than a constant times $1/n$, as you can check), and $g(n) = O(1/n)$. The convention is that the right hand side is a rougher expression of the left hand side, "$=$" here is not equality. For example, you can check that:

$\begin{align*} 3 \sqrt{n} &= O(n^3) \\ 17 n^3 &= O(n^3) \end{align*}$

but that doesn't mean $\sqrt{n} = 17 n^3$. If you use $O(\cdot)$ on the left hand side, make sure the right hand side is rougher. And "$<$" makes no sense whatsoever, any such inequality is subsumed by the $O(\cdot)$ itself.

Source Link
vonbrand
  • 14.1k
  • 3
  • 41
  • 52

That really makes no sense. Check out e.g. Hildebrand's "Asymptotic analysis" for details of the meanings and usage of asymptotic notations.

In a nutshell, for typical CS use: $O(f(n))$ is some function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n_0$ for some (again unspecified) constant $n_0$. The functions $f$ and $g$ are positive in our usage. It is meant to represent some rough upper bound, in the sense that an "equation" like:

$\begin{equation*} e^{1/n} = 1 + O(1/n) \end{equation*}$

means that $e^{1/n}$ is $1 + g(n)$ (here, by the series for $e^x$ it is $g(n) = \sum_{k \ge 1} \frac{1}{k! n^k}$) and $g(n) = O(1/n)$ (the sum of the terms after the first is smaller than a constant times $1/n$, as you can check), and $g(n) = O(1/n)$. The convention is that the right hand side is a rougher expression of the left hand side, "$=$" here is not equality. For example, you can check that:

$\begin{align*} 3 \sqrt{n} &= O(n^3) \\ 17 n^3 &= O(n^3) \end{align*}$

but that doesn't mean $\sqrt{n} = 17 n^3$. If you use $O(\cdot)$ on the left hand side, make sure the right hand side is rougher. And "$<$" makes no sense whatsoever, any such inequality is subsumed by the $O(\cdot)$ itself.