What is the difference between the complexity $O$-notation?

Question

For a rank $r,d\times d$ density matrix $\rho$, where $d=2^n$, using $O(rdlog^2d)$ measurement settings can reconstruct the density matrix, while I see another description that we need $\Omega(rd\ \mathrm{poly\ log}d)$ meaurement settings.

(1) Do the $O(rdlog^2d)$ and $\Omega(rd\ \mathrm{poly\ log}d)$ have same meaning?

(2) And What is the meaning of "$\mathrm{poly\ log}d$" in the $\Omega(rd\ \mathrm{poly\ log}d)$?

(3) Do the $\Omega$ have the same mean with $O$, and do they mean the complexity of consumed resources?

Answer 1

(1) They are not the same thing. The big $O$ defines an asymptotic upper bound or the worst-case behaviour of an algorithm. The big $\Omega$ gives the lower bound. For example, if we want to give the lower bound on the resources requirements then we use the big $\Omega$. The $O(rd \ \log^2d)$ is a very specific description of asymptotic behaviour, i.e., it tells that the scaling goes as log squared. On the other hand, the $\Omega(rd \ \textrm{poly}\log d)$ is a slightly more loose description. It just says that scaling goes as some polynomial in log. This is to say that scaling is polynomial and not exponential. In general, $\textrm{poly}$ could mean any polynomial of an arbitrary degree $n$. It could be constant, linear or quintic. In your particular case, it is reasonable to assume that $\textrm{poly}$ implies a linear polynomial.

(2) $\textrm{poly} \log$ means a polynomial in $\log$. Here is a degree $n$ polynomial in $x$, $p(x) = a_n x^n + \cdots +a_0$. Now, replace $x$ with $\log$ and you get a $\textrm{poly} \log$. Clearly $\log^2 d$ is a degree two polynomial in $\log$.

(3) I think (1) answers this.

Answer 2

The $O()$ notation indicates worst-case running time ("upper bound time complexity").

For example, if we have an unstructured list with $N$ values, then in the worst case it takes $N$ steps to find a specific value in the list and therefore the worst case complexity is $O(N)$ - i.e linear time complexity, for that specific example.

Using simple words - we can be really unlucky such that we will have to go through all the $N$ values of the unstructured list untill we find the desired value.

The $\Omega ()$ notation indicates best-case running time (“lower bound time complexity”).

Looking at the same example of finding a specific value in an unstructured list with $N$ values, the best-case complexity of this operation is $\Omega (1)$ - i.e constant time complexity.

Using simple words - in the best case we can be really lucky and find the unique value we are looking for in 1 try or few tries, doesn't matter how big is $N$. Therefore the best-case complexity is constant for that specific example.

---

About that question:

(1) Do the O(rdlog2d) and Ω(rd poly logd) have same meaning?

The answer is basically yes, take a look at this explanation for details.