オーダー記法 - 練習編

O(f(n))={g(n) | ある定数Nと定数cが存在してn\geq Nならばg(n)\leq c f(n)}である.
以下の式があっているかどうかを○×で答えよ.

  1. n=O(\log{n})
  2. n\log^2{n}=O(n^2)
  3. n^{100}=O(n^{\log{n}})
  4. 2^n=O(2^n)
  5. 2^{2n}=O(2^n)
  6. 2^{2n}=2^{O(n)}
  7. 1/\log{n}=O(1)
  8. 1/\log{n}=O(1/n)
  9. 1/n=O(1/\log{n})

こんなもんか.