Additions to ECS 20 Chapter 5.3 (Big-O/Theta/Omega)

[matthewsot]

In Section 5.3, it would be nice to clarify the somewhat confusing use of "=" when people talk about "Big-O," in that:

g(n) = O(f(n)) \wedge h(n) = O(f(n))
\not\implies g(n) = h(n)

Which always kind of freaks me out haha. I think the following should be mentioned:

1. Conventionally, we put the "less precise" representation on the right-hand side of the equals sign, like 5n = O(n), but not O(n) = 5n
2. Equals signs with O-notation should be considered "1-way," as in a = b is not the same as b = a
3. Alternatively/in addition, equations with big-O can be seen as really representing the set of all equations fulfilling those requirements.

i can also include some "gotcha" mistakes, such as O(n^3) - O(n^3) = 0 or \sum_{k=1}^n kn = \sum_{k=1}^n O(n) = O(n^2). But in Bai we really didn't focus on this so not sure if it's worth the space.

[aakash1104]

1. I agree with the confusion caused by the representation. There are two things that I have seen in the academic world regarding Big-O's. The = is replaced by \in or is sometimes written as the following: N^2 + 2N + 9 is O(N^2)

2. We could clarify this using programming analogy (C++?)

   int a = 9; // a is now set to 9
   9 = a; // This won't compile

3. One of the major things that I'd like to see (not in depth) is that Big-O does not mean how fast the algorithm runs! The other thing you could say is that the constant is always hidden in Big-O's.

4. Regarding the O(n^3) - O(n^3) = 0 and the other intricate details, I don't think we should worry about them too much. They aren't covered a lot in 20.

Otherwise, everything looks great :)