2
$\begingroup$

How come computer science books are so relaxed about specifying which set variables/values belong too ?

I've read several books on algorithms like CLRS's Introduction to Algorithms, Sedgewick's An Introduction to the Analysis of Algorithms etc.

How come these kind of books are so sloppy about telling which set values/variables belong too ?

To give some examples:

Introducing Big-O notation books don't mention the domain and co-domain of the functions $f(N)$ and $g(N)$. Neither, is it mentioned which set the constant $C$ belongs too.

Introducing Generation Functions nothing is said about the values of the sequence $a_0, a_1, \ldots$. In mathematics these are complex numbers, but nothing is said here.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Especially regarding Big-O notation, impreciseness starts even earlier. I do not understand the benefit of saying, e.g., $g(n) = \mathcal{O}(f(n))$ instead of $g(n) \in \mathcal{O}(f(n))$. $\endgroup$
    – Rmn
    Aug 6, 2014 at 10:39
  • 1
    $\begingroup$ While this is a good question in the sense that it should certainly be asked, it is not a good fit for this site. It does not admit objectively correct answers; the authors have their own reasons. Also, while this is true for some it is almost certainly not true for all CS books. $\endgroup$
    – Raphael ♦
    Aug 6, 2014 at 10:57
  • $\begingroup$ That said, I can offer some guesses: 1) The books you name are textbooks, designed to accompany a university course. The authors may assume certain prior knowledge; for instance, CLRS explicitly mention that they assume some programming and mathematical prior knowledge. 2) The details either don't matter or are clear from context. (I dislike this explanation/excuse myself, but I have heard it many times.) $\endgroup$
    – Raphael ♦
    Aug 6, 2014 at 11:03
  • $\begingroup$ The same applies to the Wikipedia article on Big-O. So it is assumed we always are in the real numbers otherwise anything else is being said ? $\endgroup$
    – Shuzheng
    Aug 6, 2014 at 12:17
  • $\begingroup$ In algorithm analysis, we even have $\mathbb{N} \to \mathbb{N}$. (I find the formal rigor in many Wikipedia articles lacking, and many of the descriptions misleading. For all but basic definitions, I can not recommend Wikipedia where TCS is concerned.) $\endgroup$
    – Raphael ♦
    Aug 6, 2014 at 12:30

0

Reset to default

Browse other questions tagged or ask your own question.