# How to compare algorithms in class NC time complexity with other classes?

I know these relations :

\begin{gather} \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\ \mathrm{NC}^i \subseteq \mathrm{AC}^i \subseteq \mathrm{NC}^{i+1} \\ \mathrm{NC}^1 \subseteq \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{AC}^1 \subseteq \mathrm{NC}^2 \subseteq \mathrm{P} \end{gather}

But I don't know how to compare an algorithm with time complexity of $\mathrm{NC}^i$ to an algorithm with Polynomial complexity?

For example, Topological sort $\mathrm{NC}^2$ with BFS $\mathcal{O}(|V| + |E|)$

The class NC is by definition a subset of P, since it consists of uniform polynomial size circuits with some restrictions (namely, polylogarithmic depth). It is unknown whether $NC \neq P$, but this is strongly suspected.
Let me comment that $O(NC^2)$ is a syntax mismatch since $NC^2$ is a complexity class rather than a function. We simply say that topological sort is in $NC^2$.
• If the circuit is uniform then the size of the circuit (corresponding to time) is exponential in its depth, so only uniform NC$^1$ is in P due to the depth. Fortunately, circuits in NC also have to be polynomial size. So you cannot generally tell from the depth anything about the running time. – Yuval Filmus Apr 2 '14 at 15:39