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

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?

• each post should contain a single, laser-focus question. You can ask different questions in separate posts. Feel free to edit the question to focus it on a specific point, adding relevant context and your current understanding where needed. See also quantumcomputing.stackexchange.com/help/how-to-ask
– glS
Commented Aug 11, 2022 at 9:45

(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.

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.