1
$\begingroup$

I found this on page 538 (resp. 576) of Introduction to Modern Cryptography 2nd (resp 3rd) edition by Katz and Lindell. The third bullet point under Example A.6 says:

$$\begin{array}{l}\text{Let }f(n)=n^4+3n+500.\text{ Then:}\\ \quad\text{(…)}\\ •\;\; f(n) = Ω(n^3 \log n).\text{ In fact, }f(n) = ω(n^3 \log n).\end{array}$$

I am just looking for a high level explanation, not a mathematical proof or something, about what this means.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ See the page 576 on the third edition. $\Omega \text{ is } \leq $ and $\omega \text{ is } < $ $\endgroup$
    – kelalaka
    Commented May 29, 2021 at 13:45

1 Answer 1

Reset to default
5
$\begingroup$

The first line in the quote now in the question defines a function $f$ of variable $n$. The last line is about how fast (the output of) that function grows when $n$ grows towards $+\infty$.

Both statements $f(n) = Ω(n^3 \log n)$ and $f(n) = ω(n^3 \log n)$ are about how fast $f(n)$ grows relative the function $g$ defined by $g(n)=n^3\log n$. The first statement roughly tells that $f(n)$ grows no slower than $g(n)$, while the second tells that $f(n)$ grows faster. Both statement are true, and easily shown so when we look at the definition of $f$ and $g$.

Update following comment:

  • The statement is strictly about the value taken by $f(n)$, not about the difficulty (time, space, cost) to compute $f$. What that value taken by $f(n)$ represents is not stated by the notation. It's not part of the definition of $f$. It could be stated by what defines the quantity $f(n)$ represents. That would often be time, or space taken by some algorithm. It could be the value of an integer like an RSA public modulus. That's untold in the question, or the whole appendix A.2 with the question's quote.
  • "grows faster" is not really the same as "greater". Sorry, to be precise, we need the mathematical definitions.

That's using a so-called (Bachmann-)Landau notation, which makes an unusual use of the $=$ sign: equality usually features transitivity. It takes some time to get used to it.

Anything more specific won't meet the "high level explanation" requirement in the question. But if we read a few lines above the question's quote in the book, or about (Bachmann-)Landau notation, the definitions are given.

It holds $f(n) = ω(g(n))\;\implies\;f(n) = Ω(g(n))$. That's why the sentence has $\text{in fact}$, often used to introduce a stronger or more precise statement, like: That's good. In fact, it's delicious.

Roughly speaking, the notation means that when $n$ grows: $$\begin{array}{ll} f(n) = \omega(g(n))&f(n)\text{ grows faster than }g(n)\\ f(n) = \Omega(g(n))&f(n)\text{ grows no slower than }g(n)\\ f(n) = \Theta(g(n))&f(n)\text{ grows as fast as }g(n)\\ f(n) = \mathcal O(g(n))&f(n)\text{ grows no faster than }g(n)\\ f(n) = o(g(n))&f(n)\text{ grows slower than }g(n)\\ \end{array}$$

Improve this answer
$\endgroup$
8
  • 5
    $\begingroup$ Instead of the equal sign, it is also (more?) common to use "element of". That might be more consistent and easier to understand. $\endgroup$
    – jjj
    Commented May 29, 2021 at 14:45
  • 1
    $\begingroup$ @questioner: please read the updated answer. The previous one was incorrect on my attempt to roughly explain $Ω$. $\endgroup$
    – fgrieu ♦
    Commented May 29, 2021 at 18:48
  • 1
    $\begingroup$ @jjj: Would we write $f(n)\in\Omega(n^3\log n)$ or $f\in\Omega(n\mapsto n^3\log n)$ or something else? Can you link to a reference using that $\in$ notation in a cryptographic context? $\endgroup$
    – fgrieu ♦
    Commented May 30, 2021 at 8:19
  • 2
    $\begingroup$ @jjj some theorists may prefer $\in$ instead of $=$. The $=$ is just an abuse of notation that almost everybody uses; O(·) is not a function, so how can a function be equal to it? $\endgroup$
    – kelalaka
    Commented May 30, 2021 at 10:34
  • 2
    $\begingroup$ @questioner: writing "FOO. In fact, BAR." is a way to state that: (a) Proposition FOO holds in the circumstance. (b) Proposition BAR holds in the circumstance. (c) BAR ⟹ FOO [though (c) is admittedly not as strongly stated as (a) and (b) are]. That's the rationale for using "In fact" in the question's quote. $\endgroup$
    – fgrieu ♦
    Commented May 30, 2021 at 12:37

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.