Big Oh And Relations 


My latest posts can be found here: Previous blog posts:
Additionally, some earlier writings: 
IntroductionIn an earlier post we saw that the function $f(n)=n$ dominates $g(n)=n\ln(n)$, but that's no surprise. What does come as a surprise is that $g$ dominates $f$. So even though for any value of $n$ greater than $2$ we already have $f(n)>g(n)$, still we say that $g$ dominates $f$. That feels very unexpected, and as a result you might question the value of the concept of "dominates", so let's pause and take a moment to get a handle on what's going on. Firstly, the fact that $b^n$ dominates $n^k$ for any $b>1$ and $k>0$ feels right and reasonable. After all, we talk about "Exponential Growth" and know that it's fast. Really fast. So the fact that exponential growth dominates polynomial growth is expected. And it's also reasonable that polynomial growth never dominates exponential growth. Stands to reason. There's a hierarchy, and exponential growth is "higher up" than polynomial growth. But what about $f$ and $g$ above? How can each "dominate" the other in this technical sense? We've looked at the technical definition, we know that according to that we have $n\ln(n)$ dominates $n$, which in turn dominates $n\ln(n)$. How can we get a handle on that? In short, we are asking about the relationships between functions.
Equivalent functionsFrom our previous post we have the idea of a "Mathematical Relation", and in particular, we have the concept of an "Equivalence Relation." Let's define a particular relation between functions. We'll say that given two functions, $f$ and $g$, then the pair $(f,g)$ is in our relation if $f$ dominates $g$ and $g$ dominates $f$. We'll call our relation $R$. As an example:
Properties of $R$The first thing to note is that $R$ is Reflexive. For any function $f$, $f$ dominates $f$, so $(f,f)$ is in $R$. The second thing to note is that it is symmetric. If $(f,g)$ is in our relation then $f$ dominates $g$ and $g$ dominates $f$. Therefore $g$ dominates $f$ and $f$ dominates $g$, and so $(g,f)$ is in $R$. Finally, we observe that $R$ is transitive. If $(f,g)$ is in $R$, and $(g,h)$ is in $R$, then $(f,h)$ is in $R$. We'll leave the confirmation of this this as an exercise for the mythical interested reader. So $R$ is reflexive, symmetric, and transitive, and hence is an "Equivalence Relation". If the pair $(f,g)$ are in $R$, then for the purposes of $R$ they are equivalent. But what is the purpose of $R$?
Equivalence Classes of FunctionsSince we have an Equivalence Relation between functions, we can now talk about the Equivalence Classes. So choose some function, say $n^2$, we can talk about all the other functions that are equivalent to it under our relation $R$. This will include:
So we can ask for a canonical representative of an Equivalence Class, and the obvious choice would seem to be to express it as the sum of functions, from among them choose the most rapidly growing term, and then ignore any leading constant coefficient. So for each Equivalence Class we have a canonical representative that is, in some sense, as simple as possible. (Cue Kolmogorov Complexity Theory).
The HierarchyNow let's consider the relationships between the Equivalence Classes. Consider two Equivalence Classes, $E_1$ and $E_2$. We can easily show that either functions from $E_1$ dominate those from $E_2$ or vice versa. You can go through the details, but what we find is that thinking of the Equivalence Classes as things in their own right, the relative dominance of their constituent functions is inherited by the Equivalence Classes to become a concept of dominance between them. As a result we have a total ordering on the Equivalence Classes. And so we come to the heart of the BigOh concept.
Putting it into actionConsider the problem SQR of squaring a given number. The "size" of the number is the number of bits, and we have various algorithms to accomplish finding the square. For our example here we will consider the naive multiplication algorithm that we learned in school, and we can ask  just how much work is that? Getting technical, we would have to give a precise definition of what we mean by a "step" in the algorithm, but speaking somewhat loosely we can see that if we have $d$ digits, the central section of the multiplication will have $d^2$ entries, and then we have to do some additions in each of up to $2d1$ columns, etc. We therefore can see that the number of "steps" is some constant $k$ times $d^2$ plus some lower order terms, so the answer is something like:
This is a function in some equivalence class, and we can use the canonical representative of that class, which is $d^2$. Let's call the true "timerequired" function $M(n)$. It's really quite complicated, but we now know that $d^2$ dominates $M$, and $M$ dominates $d^2$. So we may as well say that the timecomplexity of this algorithm is $d^2$. And that's what we do. The "BigOh" complexity of this algorithm is $n^2$, so the algorithm is said to be $O(n^2)$. (Getting set soon to write some details of how we use these ideas as we analyse specific algorithms.)
Send us a comment ...

Quotation from Tim BernersLee 