Apakah fungsinya selalu sebanding secara asimptotik?

Ketika kita membandingkan kompleksitas dari dua algoritma, biasanya kasusnya adalah atau g ( n ) = O ( f ( n ) ) (mungkin keduanya), di mana f dan $f(n) = O(g(n))$$g(n) = O(f(n))$$f$$g$ adalah waktu berjalan (misalnya) dari kedua algoritma.

Apakah ini selalu terjadi? Yaitu, apakah setidaknya salah satu dari hubungan dan g ( n ) = O ( f ( n ) ) selalu berlaku, yaitu untuk fungsi umum f , g ? Jika tidak, asumsi mana yang harus kita buat, dan (mengapa) tidak apa-apa ketika kita berbicara tentang algoritma yang menjalankan waktu?$f(n) = O(g(n))$$g(n) = O(f(n))$$f$$g$

Tidak setiap pasangan fungsi sebanding dengan notasi ; pertimbangkan fungsi f ( n ) = n dan g ( n ) = { 1 jika  n  adalah ganjil , n 2 jika  n  adalah genap . Selain itu, fungsi-fungsi seperti g ( n ) memang muncul sebagai waktu menjalankan algoritma. Pertimbangkan algoritma brute-force jelas untuk menentukan apakah integer diberikan n adalah prima:$O(\cdot)$$f(n) = n$

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

Algoritma ini membutuhkan operasi aritmatika ketika $\Theta(1)$$n$ adalah genap, operasi ketikanadalah komposit, tetapiΘ(n)beroperasi ketikanadalah prima. Dengan demikian, secara formal, algoritma initidakdapatdibandingkandengan algoritma yang menggunakan$O(\sqrt{n})$$n$$\Theta(n)$$n$ operasi aritmatika untuksetiapn.$\sqrt{n}$ $n$

Sebagian besar waktu ketika kita menganalisis algoritma, kita hanya menginginkan batas atas asimtotik dari bentuk untuk beberapa fungsi yang relatif sederhana f . Misalnya, sebagian besar buku teks hanya akan (dan benar) melaporkan yang berjalan dalam operasi aritmatika O ( n ) . Fungsi batas atas yang tipikal adalah produk dari eksponensial, polinomial, dan logaritma (walaupun lebih banyak binatang eksotik seperti faktorial dan logaritma iterasi juga muncul sesekali). Tidak sulit untuk membuktikan bahwa dua fungsi tersebut dapat dibandingkan.$O(f(n))$$f$IsPrime(n)$O(n)$

Lihat juga pertanyaan MathOverflow ini .

Dari wikipedia, definisi notasi O besar:

$x$$f(x)$$g(x)$$f(x) \in O(g(x))$$M$$x_0$

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

Apa yang terjadi untuk fungsi yang tidak konvergen (ke konstan atau tak terhingga)?

$f(x) = |xsin(x)|$, and $g(x) = 10$

for each $x_0$, there is some $x > x0$, such that $x = k\pi$, thus $f(x) = 0$ - so for each $M$ - $Mf(x) > g(x)$ will yield false, and $g(x) \; \not\in O(f(x))$

However, it is easy to see that $|xsin(x)|$ is not bounded by any constant as well, thus for each $M$,$x_0$, there is some $x > x_0$ such that $f(x) < Mg(x)$ will also yield false, and $f(x) \not\in O(g(x))$

Note: for definition if big O that allows a maximum constant difference between $Mf(x)$ and $g(x)$, the same idea will apply with $g(x) = \log(x)$

Here's a pair monotonic functions that are not asymptotically comparable. This is relevant because most complexities arising in practice are in fact monotonic.

Here, $\Gamma$ is the gamma function. The second function is specially constructed to be very similar to the factorial, just "sampled" at slightly offset points in the gamma function. The functions cross each other periodically in such a way that neither is asymptotically bound by the other.

Let $\mathcal{L}$ be the class of functions obtained from the identity function and constants using the following operations: addition, subtraction, multiplication, division, logarithm and exponential. For example, $\exp(2\sqrt{\log x + \log\log x})/x^2$. Hardy proved that for every two functions $f,g \in \mathcal{L}$ which are positive and tend to infinity, one of the following is true: $f = o(g)$, $f = \omega(g)$, $f/g$ tends to a constant. See page 18 of his book "Orders of infinity".

The upshot is that any two "simple" functions occurring in the analysis of algorithm are comparable. Here "simple" means that there is no definition by cases (other than finitely many base cases), and no surprising functions appear, such as the inverse Ackermann function which sometimes figures in running times.