大 O 只给出渐近上界，而大 Theta 也给出下界。
一切都是Theta(f(n))，O(f(n))但不是相反。
T(n)据说是Theta(f(n))，如果它既是 又O(f(n)) 是 Omega(f(n))
出于这个原因，big-Theta 比 big-O表示法提供更多信息，所以如果我们可以说某个东西是 big-Theta，它通常是首选。然而，证明某事物是大 Theta 比证明它是大 O 更难。
例如，归并排序既是O(n*log(n))and Theta(n*log(n))，但也是 O(n 2 )，因为 n 2比它渐近“大”。但是，它不是 Theta(n 2 )，因为算法不是 Omega(n 2 )。
Omega(n)是渐近下界。如果T(n)是Omega(f(n))，则表示从某一个开始n0，有一个常数C1这样的T(n) >= C1 * f(n)。而 big-O 表示存在一个常数C2，使得T(n) <= C2 * f(n)).
所有三个（Omega、O、Theta）都只给出渐近信息（“对于大输入”）：
请注意，此符号与算法的最佳、最差和平均情况分析无关。这些中的每一个都可以应用于每个分析。
我将仅引用Knuth 的 TAOCP 第 1 卷- 第 110 页（我有印度版）。我建议阅读第 107-110 页（第 1.2.11 节渐近表示）
人们经常通过假设 O 表示法给出了确切的增长顺序来混淆 O 表示法。他们使用它，就好像它指定了一个下限和一个上限一样。例如，一个算法可能被称为低效率，因为它的运行时间是 O(n^2)。但是运行时间为 O(n^2) 并不一定意味着运行时间也不是 O(n)
在第 107 页，
1^2 + 2^2 + 3^2 + ... + n^2 = O(n^4) 和
1^2 + 2^2 + 3^2 + ... + n^2 = O(n^3) 和
1^2 + 2^2 + 3^2 + ... + n^2 = (1/3) n^3 + O(n^2)
Big-Oh 用于近似值。它允许您将 ~ 替换为等号 = 符号。在上面的例子中，对于非常大的 n，我们可以确定数量将保持在 n^4 和 n^3 和 (1/3)n^3 + n^2 [而不仅仅是 n^2] 以下
Big Omega 用于下界 - 对于大 N，使用 Omega(n^2) 的算法不会像使用 O(N logN) 的算法那样有效。但是，我们不知道 N 的值是多少（从这个意义上说，我们知道大约）
Big Theta 用于精确的增长顺序，包括下限和上限。
如果运行时间用大 O 表示法表示，你知道运行时间不会比给定的表达式慢。它表达了最坏的情况。
但是使用 Theta 表示法，您也知道它不会更快。也就是说，没有最佳情况下算法会更快地重新调整。
这给出了对预期运行时间的更精确限制。然而，对于大多数目的，忽略下限（更快执行的可能性）更简单，而您通常只关心最坏的情况。
我将用一个例子来说明差异。
让函数 f(n) 定义为
if n is odd f(n) = n^3
if n is even f(n) = n^2
来自 CLRS
如果存在正常数 c1 和 c2，则函数 f(n) 属于集合 Θ(g(n))，因此对于足够大的 n，它可以“夹在”c1g(n) 和 c2g(n) 之间。
和
O(g(n)) = {f(n)：存在正常数 c 和 n0 使得对于所有 n ≥ n0 0 ≤ f(n) ≤ cg(n)}。
和
Ω(g(n)) = {f(n)：存在正常数 c 和 n0 使得 0 ≤ cg(n) ≤ f(n) 对于所有 n ≥ n0}。
f(n) 的上限是 n^3。所以我们的函数 f(n) 显然是 O(n^3)。
但它是Θ（n ^ 3）吗？
为了使 f(n) 在 Θ(n^3) 中，它必须夹在两个函数之间，一个形成下界，另一个形成上界，两者都在 n^3 处增长。虽然上限很明显，但下限不能是 n^3。下限实际上是 n^2；f(n) 是 Ω(n^2)
来自 CLRS
对于任何两个函数 f(n) 和 g(n)，我们有 f(n) = Θ(g(n)) 当且仅当 f(n) = O(g(n)) 和 f(n) = Ω(g(n))。
因此 f(n) 不在 Θ(n^3) 中，而在 O(n^3) 和 Ω(n^2) 中
这是我的尝试：
一个函数f(n)是O(n)，当且仅当存在一个常数 ，c，使得f(n) <= c*g(n)。
使用这个定义，我们可以说函数f(2^(n+1))是O(2^n)吗？
换句话说，是否'c'存在这样的常数2^(n+1) <= c*(2^n)？注意第二个函数 ( 2^n) 是上述问题中大 O 之后的函数。起初这让我很困惑。
所以，然后使用你的基本代数技能来简化这个方程。 2^(n+1)分解为2 * 2^n。这样做，我们剩下：
2 * 2^n <= c(2^n)
现在很简单，该等式适用于cwhere的任何值c >= 2。所以，是的，我们可以说f(2^(n+1))是O(2^n)。
Big Omega 的工作方式相同，除了它对某些常量计算f(n) >= 。c*g(n)'c'
因此，以同样的方式简化上述函数，我们得到了（注意 >= now）：
2 * 2^n >= c(2^n)
因此，该等式适用于范围0 <= c <= 2。所以，我们可以说f(2^(n+1))是大欧米茄(2^n)。
现在，由于两者都成立，我们可以说函数是 Big Theta ( 2^n)。如果其中一个不能用于常数'c'，那么它就不是 Big Theta。
上面的例子取自 Skiena 的 Algorithm Design Manual，这是一本很棒的书。
希望有帮助。这确实是一个很难简化的概念。不要太纠结于什么'c'，只需将其分解为更简单的术语并使用您的基本代数技能。
在非常简单的语言中，差异是这样的：
大 O 表示法用于算法的最坏情况分析。Big Omega 用于算法的最佳案例分析。当最佳情况和最坏情况分析相同时，Big Theta 用于分析算法。
假设您正在使用二进制搜索算法在排序数组中查找一个数字。
[1 2 3 4 5 6 7]
在最坏的情况下，例如当目标为 1 时，它必须执行 log(n) 拆分检查，在我们的例子中是 log(7)。它可以表示为 O(n)。
在最好的情况下，当目标为 3 时，它只执行一项操作。可以表示为Ω(1)