\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Cryptography Seminar, Spring 1993
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\naturals}{{\bf N}}
\newcommand{\reals}{{\bf R}}
\newtheorem{definition}{Definition}
\newtheorem{fact}{Fact}
\newcommand{\set}[2]{\bigl\{\, #1 \,\big|\, #2 \,\bigr\}}
\newcommand{\implies}{\;\Rightarrow\;}
\newenvironment{proof}{\noindent{\sc Proof:~}}{\hfill$\Box$\par\medskip}
\newcommand{\infinity}{\infty}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Notes on Big-Oh \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Date: \today  \\
         Burt Rosenberg\end{flushright}}}}


\subsection*{Introduction}

The Big-Oh notation is utilized to analyze the run time of algorithms.
The idea is to avoid considering algorithms which differ by ``constant
factors''. The distinction should be maintained between algorithm and
program. A program's run time depends on constant factors, an algorithm's
does not. 

Numerous variants of the Big-Oh notation can be proposed.
Jan Plaza and I investigated the consequences of changing definitions.
The second section attempts to understand the situation
using the techniques of universal-algebra.

We take $\naturals$ to be the naturals, $0,1,2,\dots$ and $\reals$
to be the reals. We consider the space of functions ${\cal F}:
\naturals\rightarrow\reals$. 

\begin{definition}
Let $g\in{\cal F}$. Define,
\[
   O(g) = \set{f\in{\cal F}}
    {\exists B, C > 0,\; \forall n > B,\; f(n) < C\,g(n)}.
\]
\end{definition}
And prove the following three facts.
\begin{fact}
Let $g\in{\cal F}$. Define,
\[
   O_1(g) = \set{f\in{\cal F}}
    {\exists C > 0,\; \forall n ,\; f(n) < C\,g(n)}.
\]
Then for any $g\in{\cal F}$ such that $g>0$, and any $f\in{\cal F}$,
\[ f\in O(g) \iff f\in O_1(g). \]
\end{fact}
\begin{proof}
It is clear that $O_1(g) \subseteq O(g)$. Suppose $f\in O(g)$, and fix
$B$ and $C$ as required by the definition of $O(g)$.
Let,
\[ D = \max_{i=0,\ldots,B}\{\,f(i)/g(i)\,\} +1. \]
This is possible since $g>0$.
Let $C' = \max( C,D)$.
For $n>B$,
\[ C' g(n) \ge C g(n) > f(n),\]
and for $n \le B$,
\[ C' g(n) \ge D g(n) \ge (f(n)/g(n) + 1) g(n) > f(n).\]
Hence $f\in O_1(g)$.
\end{proof}
\begin{fact}
Let $g\in{\cal F}$. Define,
\[ 
  O_2(g) = \set{f\in{\cal F}}
  {\exists B, C > 0,\; \forall n>B,\; f(n) < C\max\bigl(g(n),1\bigr)}.
\]
Then for every $g\in{\cal F}$ which is positive and nondecreasing
on a certain interval $[a,\infinity)$,
\[ f\in O(g) \iff f\in O_2(g). \]
\end{fact}
\begin{proof}
From $g(n) \le \max(g(n),1)$ follows $O(g) \subseteq O_2(g)$.
Suppose $f\in O_2(g)$, and fix $B$ and $C$ as required by the
definition of $O_2(g)$. Let,
\[C'= C\max(1,1/g(a)).
\]
For all $n\ge a$, 
\[ C' g(n) \ge C g(n)/g(a) \ge C.\]
Therefore, for all $n > \max( a, B ) $,
\[ C' g(n) = \max(C'g(n),C) \ge \max(Cg(n),C) = C \max(g(n),1) > f(n).\]
Hence, $f \in O(n)$.
\end{proof}
The positive and nondecreasing supposition is needed, as
$1/n = O_2(1/n^2)$ however $1/n \neq O(1/n^2)$. 
\begin{fact}
For $f,g\in{\cal F}$, $f\in O(g) \implies f\in O_2(g)$.
\end{fact}
\begin{proof}
This is shown in the first sentence of the preceding proof.
\end{proof}

\noindent{\sc Remark: }
Typically, $f\in O(g)$ is written $f=O(g)$.

\subsection*{The algebraic viewpoint}

There is another way to look at these results.
Recall that a {\em preorder} is a relation $\le$ such that,
\begin{enumerate}
\item The relation is reflexive: $a \le a$,
\item The relation is transitive: $a \le b$ and $b \le c$ implies $a\le c$.
\end{enumerate}
The following is a preorder on ${\cal F}$:
\[ f \le g \iff f \in O(g).\]
For a preorder to be a {\em partial order}, anti-symmetry must hold,
\[ a \le b \mbox{  and  } b \le a \mbox{  implies } a = b, \]
in the sense that ``they are the same object''.
Obviously, $\le$ is not a partial order. 
Desiring a partial order, we make it one by a general technique:
\begin{definition}
Two functions $f, g \in {\cal F}$ are said to be theta-equivalent
if 
\[f \le g \mbox{  and  } g \le f.\]
\end{definition}
We write $\Theta(f)$ for the class of functions theta-equivalent to $f$,
and $\Theta({\cal F})$ for the set of all theta-equivalence
classes, the image of ${\cal F}$ under $\Theta$.

\begin{fact}
Define the relation $\le$ on $\Theta({\cal F})$ as follows.
Given any two elements $\theta_1$ and $\theta_2$
from $\Theta({\cal F})$ and any two functions $f_1\in\theta_1$ and
$f_2\in\theta_2$,
\[ \theta_1 \le \theta_2 \iff f_1 \le f_2. \]
Then $\le$ is a partial order on $\Theta({\cal F})$.
\end{fact}
\begin{proof}
First, we demonstrate the relation is well-defined. Suppose
$f_1$ and $f_2$ are taken from $\theta_1$ and $\theta_2$, respectively,
and that $f_1\le f_2$. If $g_1$ and
$g_2$ are other choices from $\theta_1$ and
$\theta_2$, respectively, then,
\[g_1\le f_1\le f_2\le g_2,\]
so $f_1\le f_2$ irrespective of the choice of test elements.

The relation $\le$ on $\Theta({\cal F})$ is reflexive: for any
$\theta\in\Theta({\cal F})$, take any $f\in\theta$. Since $f\le f$
then $\theta\le\theta$.

The relation $\le$ on $\Theta({\cal F})$ is transitive: let
$\theta_1, \theta_2, \theta_3\in \Theta({\cal F})$ be such that
$\theta_1\le\theta_2$ and $\theta_2\le\theta_3$. There
exist $f_1\in\theta_1, f_2\in\theta_2,$ and $f_3\in\theta_3$ such
that $f_1\le f_2$ and $f_2\le f_3$. Therefore $f_1\le f_3$ hence
$\theta_1\le\theta_3$.

The relation $\le$ on $\Theta({\cal F})$ is anti-symmetric:
let $\theta_1$ and $\theta_2$ be elements of $\Theta({\cal F})$
for which $\theta_1\le\theta_2$ and $\theta_2\le\theta_1$.
Since for all $f_1$ taken from $\theta_1$ and all $f_2$ taken
from $\theta_2$, both $f_1\le f_2$ and $f_2\le f_1$, all
such pairs are theta-equivalent. This means that any $f_1$
in $\theta_1$ is also in $\theta_2$, and vice-a-versa. So $\theta_1
=\theta_2$.
\end{proof}

In order to make the notation less cumbersome, we shall
simply write $\Theta$ for $\Theta({\cal F})$. We have a special
interest in the class $\Theta(1)$ in $\Theta$ and give it the name $1$.
Starting from preorder $O_2$ we can construct a
partial order $\Theta_2$ in the exact same manner that $\Theta$
was constructed from $O$. The function $\Theta_2(f)$ will take
an $f\in{\cal F}$ to its equivalence class in $\Theta_2$.
Its class $\Theta_2(1)$ will also be denoted $1$. Which $1$ will be
discernible from context.

Let $A$ and $B$ be two partial orders whose ordering is denoted
generically by $\le$. A map $f:A\rightarrow B$ is {\em order-preserving}
if,
\[ a \le b \implies f(a) \le f(b).\]

\begin{fact}
The following is a well-defined order-preserving map:
\[\begin{array}{clcl}
    \phi: & \Theta & \rightarrow & \Theta_2 \\
          & \theta & \mapsto & \Theta_2(f), \mbox{ for any $f\in\theta$.}
\end{array}
\]
And claim:
\begin{enumerate}
\item For any $\theta\in\Theta_2,\; 1\le\theta$. That is, $1$
is the smallest element in $\Theta_2$. 
\item For all $\theta\in\Theta$ such that $\theta\le 1,\; \phi(\theta)=1$.
\item The restriction of $\phi$ to $\set{\theta\in\Theta}
{\theta\ge 1}$ is injective.
\end{enumerate}
\end{fact}
\begin{proof}
Well-definedness follows from $O(f)\subseteq O_2(f)$: let $f$ and
$g$ be from $\theta$. Then $f \in O(g) \implies f\in O_2(g)$ and
$g\in O(f) \implies g\in O_2(f)$, so $f$ and $g$ are theta-equivalent
by $\Theta_2$.

Take $\theta_1, \theta_2 \in \Theta$ such that $\theta_1\le \theta_2$.
Choosing $f_1\in\theta_1$ and $f_2\in\theta_2$,
\[ f_1\in O(f_2) \implies f_1\in O_2(f_2).\]
Therefore, $\phi(\theta_1)\le\phi(\theta_2)$.

Given any $f$, take $B, C=1$ in the definition of $O_2$ to
verify $1\in O_2(f)$, that is $\Theta_2(1)\le\theta$ for any $\theta\in\Theta_2$.
Because the map is order-preserving, if $\theta\le\Theta(1)$
then $\phi(\theta)\le\Theta_2(1)$. However $\Theta_2(1)\le\phi(\theta)$. So $\phi(\theta)=\Theta_2(1)$.

Select the function $1(n)=1$ from the class $1\in\Theta$.
The statement $\theta_1, \theta_2 \ge 1$ translates to:
\[ \forall f\in\theta_i\; \exists C, B > 0 \mbox{ s.t. }
  \forall n> B,\; 1<Cf(n).\]
We can therefore select from $\theta_i$ an $f_i$ for which
$f(n)>1$ for all $n$. In which case $\max(f_i(n),1)=f_i(n)$ for
all $n$. Hence if $f_1\le f_2$ then $f_1\le f_2$ and if
$f_2\le f_1 $ then $f_2\le f_1$. Putting this together,
if $\Theta_2(f_1)=\Theta_2(f_2)$ then $\Theta(f_1)=\Theta(f_2)$.
This proves the remark about injectivity.
\end{proof}
In summary, the algebraic approach sums up the difference between
$O$ and $O_2$ definitions by the following picture:

\newcommand{\mydiamond}{\begin{picture}(0,0)
\put(0,0){\line(1,1){30}}
\put(30,30){\line(1,-1){30}}
\put(60,0){\line(-1,-1){30}}
\put(30,-30){\line(-1,1){30}}
\end{picture}}

\newcommand{\xoff}{80}
\newcommand{\yoff}{-30}

\begin{picture}(50,100)
\put(\xoff,\yoff){\begin{picture}(0,0)
\put(0,0){\mydiamond}
\put(0,60){\mydiamond}
\put(120,60){\mydiamond}
\put(30,30){\circle*{5}}
\put(15,25){$1$}
\put(150,30){\circle*{5}}
\put(135,25){$1$}
\put(45,30){\vector(1,0){85}}
\put(45,-30){\vector(3,2){85}}
\put(45,60){\vector(1,0){85}}
\put(70,65){injective}
\put(30,100){$\Theta$}
\put(150,100){$\Theta_2$}
\put(85,100){$\stackrel{\textstyle\phi}{\longrightarrow}$}
\end{picture}}
\end{picture}


\end{document}
