Return to Answer

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 represents is not stated by the notation. It's stated by what defines the quantity $f$ represents. That could be time, or space, or the value of an integer like an RSA public modulus; we can't tell.
• "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}$$

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}$$

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 or cost to compute $f$. What that value represents is not stated by the notation. It's stated by what defines what $f$ represents. That could be time, or effort, or memory/space, or the value of an integer like an RSA public modulus; we can't tell.
• "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}$$

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 represents is not stated by the notation. It's stated by what defines the quantity $f$ represents. That could be time, or space, or the value of an integer like an RSA public modulus; we can't tell.
• "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}$$

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 or cost to compute $f$. What that value represents is not stated by the notation. It's state by what defines what $f$ represents. That could be time, or effort, or memory, or the value of an integer, like an RSA public modulus; we can't tell.
• "grows faster" is not really the same as "greater". Sorry, to be precise, we need the mathematical definition.

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 can be shown $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.

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 or cost to compute $f$. What that value represents is not stated by the notation. It's stated by what defines what $f$ represents. That could be time, or effort, or memory/space, or the value of an integer like an RSA public modulus; we can't tell.
• "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}$$