0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$ Feb 8 at 5:22
  • $\begingroup$ cs 1 cs 2 $\endgroup$
    – kelalaka
    Feb 8 at 9:33
  • $\begingroup$ 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 $\endgroup$
    – questioner
    Feb 8 at 21:52
  • 1
    $\begingroup$ As far as I could find some sources refer to Ω as W.eg. 1,2 $\endgroup$ Feb 9 at 14:14
  • 1
    $\begingroup$ it is Capital omega for Ω $\endgroup$ Feb 11 at 9:48
2
$\begingroup$

In general these definitions are similar everywhere and you can find a definition on Wikipedia.

Also, there is some silly confusion here. You are looking at the wrong thing! You are looking at "Proposition A.2" but you need Chapter/Section A.2 right below. enter image description here

$\endgroup$
3
  • $\begingroup$ Could you turn those images into MathJax? $\endgroup$
    – kelalaka
    Feb 8 at 11:30
  • $\begingroup$ I really appreciate that your post. Would you mind updating it with a simple example of each one, with some small numbers? I am reading through the links posted in this article but I am not exactly smart. $\endgroup$
    – questioner
    Feb 8 at 17:01
  • $\begingroup$ 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 $\endgroup$
    – questioner
    Feb 8 at 21:52

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.