# What does this Big-O notation mean based on appendix?

I am reading the following book: Introduction to Modern Cryptography Second Edition by Jonathan Katz and Yehuda Lindell.

I am going through page 533 where they list what some of the notation means, and I came across the following:

$$O(·)$$, $$Θ(·)$$, $$Ω(·)$$, $$ω(·)$$ see Appendix A.2

I believe the first symbol is the Big-O notation, but what are the other symbols called? Do they all do the same thing?

I found Appendix A.2 mentioned above on page 537 which says:

PROPOSITION A.2 For all $$x ≥ 1$$ it holds that $$(1 − 1/x)^x ≤ e^{−1}$$.

However, I have no idea what this appendix definition is trying to say. I could not even begin to guess as I do not know what the e is. Could someone please explain this to me? I am very new to both maths and cryptography.

This video explained things well, especially the second post on the video. However, it did not cover what Big-W does, or even what the "W" symbol is called.

• f(x) = Ω(g(x)) if there exists x0,c s.t. for all x>x0 cg(x)<f(x). f(x) = Θ(g(x)) if f(x) = O(g(x)) and f(x) = Ω(g(x)) So for O,Ω,Θ you can check for more details here Also ω,o are same as O,Ω but with equality – Girish Srivatsa Feb 8 at 5:22
• – kelalaka Feb 8 at 9:33
• This [video][1] explained things well, especially the second post on the video. However, it did not cover what Big-W does, or even what the "W" symbol is called. [1]: youtube.com/watch?v=6Ol2JbwoJp0 – questioner Feb 8 at 21:52
• As far as I could find some sources refer to Ω as W.eg. 1,2 – Girish Srivatsa Feb 9 at 14:14
• it is Capital omega for Ω – Girish Srivatsa Feb 11 at 9:48