Talk:Algorithms/Mathematical Background

From Wikibooks, the open-content textbooks collection

Contents 1 Use Set Notation? 2 Little-o vs. Small-o 3 i wannt to knw 4 Undefined Logical Negation symbol under types of relations

[edit] Use Set Notation?

Let's have a discussion about just using set notation for big-O. I think instead of saying that

and

f(n) = O(g(n))

We should use the set notation only:

and

We could still define what the "="s notation means, and mention that it's also used. But it would be nice to avoid these notational issues and follow the "newer" trend and adopt the set notation. We still would say "T(n) is O(n)" instead of "T(n) is in O(n)", because "is" in English is commonly understood to be in only one direction, not both. --MShonle 19:39, 1 Jan 2005 (UTC)

Introduction to Algorithms by Thomas Cormen, et. al. (ISBN 0-262-03293-7) explains its use of = by pointing out that sometimes we will want to say 3n² + 2n - 17 = 3n² + Θ(n) or even 3n² + Θ(n) = Θ(n²), which don't work if we just replace = with ∈. So it's probably better to keep = and just explain what it means.

Good point, we shouldn't get too far off the beaten path. We could leave the set interpretation as just a side note. MShonle 05:16, 21 Jan 2005 (UTC)

Anyway, in order to understand any of this, readers need a basic understanding of set theory, or at least its notation. Discrete_mathematics/Set_theory, Wikipedia:Naive set theory, and Wikipedia:Set all have basic summaries of the needed notation which could be copied here. I like Wikipedia:Naive set theory's best. Was there any resolution to the discussion at Wikibooks:Staff_lounge#Approach_to_Mathematics_Wikibooks? --jyasskin 01:36, 21 Jan 2005 (UTC)

Hey Jyasskin: BTW, Thanks for your contributions. There was no resolution with how to handle Mathematics books (and the like). For this book I'd like to see it be as self-contained as possible (it assumes the sister book on Data Structures, however it doesn't assume all of Data Structure book's content either). I think it would be safe to assume some knowledge of descrete math, but we wouldn't want to demonstrate, say, the continuum hypothesis.

Also, we'd probably want to use more examples than the wikipedia. For example, defining some natural sets along with the notation right away just so the material won't seem so abstract. A section on Set Theory right after the Mathematical Definitions sounds good. (Or perhaps you might like set theory first, to introduce relations too, which the Mathematical Definitions section uses). MShonle 05:16, 21 Jan 2005 (UTC)

[edit] Little-o vs. Small-o

I always called what you call "small-o" "little-o."

http://mathworld.wolfram.com/Little-oNotation.html

That makes sense. Thanks. MShonle 03:50, 7 September 2005 (UTC)

[edit] i wannt to knw

Bold text

[edit] Undefined Logical Negation symbol under types of relations

In describing the different types of relations, the logical negation symbol is used, for instance in defining irreflexive. However nowhere before that point or around it a suitable interpretation of that symbol is provided. Besides the interpretation is going to depend on the particular relation being defined and its set. --Balbir Thomas 17:00, 21 January 2008 (UTC)