Lesson 9

Finally, note that in the literature instead of \(f(n) \preceq g(n)\) it is often written \(f(n)=O(g(n))\) or \(f(n) \in O(g(n))\). We use the notation \(\preceq\) because in this context it seems more natural to us: it better reflects the words “not faster”, and allows comparing more than two functions in one line and writing \(\log_{2}{n}\prec n^{3} \prec 2^{n}\).