big-theta - 大きなシータ、小さなオハイオ州、小さなオメガを制限付きでチェックしていますか?

Question

f(n) と g(n) という 2 つの関数があるとします。f(n) が小さいか o(g(n)) かどうかを確認したい場合は、次のようにします。

lim n -> infinity f(n)/g(n) and the result would have to = 0 ?

上記が 0 になった場合、f(n) は o(g(n)) ということになりますか? そして、制限付きの大きなシータと小さなオメガをどのように確認できますか?

Answer 1

はい。

o(g(n)) = { f(n): すべての定数 c > 0 に対して、すべての n ≥ n0 に対して 0 ≤ f(n) < cg(n) となるような定数 n0 が存在します}。また: 0 = lim f(n)/g(n)