ベストケースと最悪の場合、時間の複雑

Question

は、アレイ

x = 0 
    for i = 0 to n - 2 
    for j = i to n - 1 
     if A[i] > A[j]: 
      x = x + 1 
    return x 

については、以下の擬似コードを付与され、最悪の場合の複雑さはO（n^2）または、なぜシータ（N^2）と？私は2つの違いを理解していないようです。

最高の複雑さについては、アルゴリズムが同じ行を実行しなければならないため、最悪の場合の複雑さと同じではありませんか？

Answer 1

このアルゴリズムの支配的な操作は、比較A[i] > A[j]です。この比較はです。常にがn^2回実行されました。

O（n^2）は、これが最悪の場合の複雑さを意味します。 O表記法を使用する場合、この複雑さは最良の場合にはより良いと言います。

シータ（n^2）は、すべての場合の複雑さを意味します。

答えは：Theta（n^2）は最高と最悪の両方でn^2なので複雑さです。

は参照してください。助けをBig-Theta notationとBig-O notation