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.

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

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you turn those images into MathJax? $\endgroup$
    – kelalaka
    Commented Feb 8, 2021 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
    Commented Feb 8, 2021 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
    Commented Feb 8, 2021 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.