19
$\begingroup$

I am a computer scientist, and one of my professors today used the symbol $\propto$. I tried to search that using google, but it returns no results, and I do not even know its name.

So, I would like to ask, what does the operator $\propto$ mean? What is its name, and how is it used?

$\endgroup$
  • 1
    $\begingroup$ The relation $\propto$ is an equivalence relation that relates from the set $A$ to $B$ and can be defined as the set $\{(a, b)\in A\times B:a=kb\}$ for some constant $k$. $\endgroup$ – Ali Caglayan Jan 26 '14 at 18:19
30
$\begingroup$

$A\propto B$ means that $A$ is directly proportional to $B$. This means that $A=kB$ for some constant $k$.

$\endgroup$
6
$\begingroup$

Since you say you're a computer scientist, it should be mentioned that Garey & Johnson use $A \propto B$ in their book Computers and Intractability – A guide to the Theory of NP-Completeness [1, page 34] to mean that there is a polynomial transformation from $A$ to $B$.

[1] Michael R Garey and David S Johnson. Computers and intractability, volume 174. Freeman New York, 1979.

$\endgroup$
3
$\begingroup$

Besides direct proportionality, you might also see something like $$ \frac{4n^2+1}{n}\propto n \text{ as }n\to\infty$$ which might rigorously be defined as: $$ \exists C \forall \varepsilon>0 \exists N\forall n>N: \left|\frac{4n^2+1}{n}-Cn\right|<\varepsilon $$ meaning there exists a constant $C$ such that for large $n$, $\frac{4n^2+1}{n}$ is approximately equal to $Cn$ (and in this case $C=4$).

edit:
The definition I gave above is very strong, you might weaken it to $$ \exists c_1,c_2\exists N\forall n>N: c_1n<\frac{4n^2+1}{n}<c_2n $$ in which case we would also have $\frac{4n^2+1}{n}+\sin(n)\propto n$ (which would make sense because the sine becomes less important as $n$ grows).

$\endgroup$
  • 2
    $\begingroup$ This is very common especially in older books; new books tend to use big-O notation and its variants, so that the statement would be written as $\frac{4n^2+1}{n}\in\Theta(n)$. Physics also tends to use it for the behavior of e.g. a field strength. $\endgroup$ – Steven Stadnicki Jan 27 '14 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.