Notasi Big-OH

Fungsi pertumbuhan seringkali dideskripsikan dengan sebuah notasi khusus. Dengan mengikuti definisi didiskripsikan notasi tersebut.

Definisi 2.2

Diberikan f dan g suatu fungsi dari himpunan bilangan integer atau himpunan bilangan real pada suatu himpunan bilangan real. Dikatakan f(x) adalah O(g(x)) jika terdapat sebuah konstanta C dan k sedemikian sehingga :

| f(x) | < C | g(x) |

Dimana x > k, dibaca f(x) adalah “big-oh” pada g(x).

Penjelasan :

Untuk menunjukkan f(x) adalah O(g(x)), hanya dibutuhkan untuk menemukan satu pasangan konstanta C dan k sedemikian sehingga | f(x) | < C|g(x)| jika x > k. Pasangan C, k yang memenuhi definisi tidak pernah tunggal. Selanjutnya, jika satu pasangan ada, maka terdapat tak terbatas pasangan yang lain. Sebuah cara sederhana untuk melihat hal tersebut adalah, jika C, k adalah satu pasangan, pasangan yang lain C’, k’ dengan C < C’ dan k < k’ juga memenuhi definisi, jika :

| f(x) | < C|g(x)| < C’ | g(x) | dimana x > k’ > k.

Contoh 1 :

Tunjukkan bahwa f(x) = x² + 2 x + 1 adalah O(x²).

Penyelesaian :

Jika 0 < x² + 2 x + 1 < x² + 2 x² + x² = 4 x² dimana x > 1, mengikuti f(x) adalah O(x²).untuk menerapkan definisi pada notasi big-O, ambil C = 4 dan k = 1. disini tidak perlu menggunakan nilai absolute jika semua fungsi pada persamaan ini adalah positif ketika x bernilai positif.

Pendekatan yang lain adalah jika x > 2, maka 2 x < x². akibatnya jika x > 2, terlihat bahwa :

0 < x² + 2 x + 1 < x² + x² + x² = 3 x²

Dari definisi didapat C = 3 dan k = 2.

Pengamatan pada relasi f(x) adalah O(x²), x² dapat diganti dengan sebarang fungsi yang lain dengan nilai yang lebih besar dari x², misalnya f(x) adalah O(x³), f(x) adalah O(x²+2x+7) dan seterusnya. Hal ini juga benar bahwa x² adalah O(x²+2x+1), jika x² < x² + 2x +1 dimana x > 1.

Dari contoh tersebut diperoleh dua fungsi, f(x) = x² + 2 x + 1 dan g(x) = x², sedemikian sehingga f(x) adalah O(g(x)) dan g(x) adalah O(f(x)).

Pernyataan terakhir dari pertidaksamaan x² < x² + 2 x + 1, dimana untuk semua x bilangan real tidak negative. Dikatakan kedua fungsi f(x) dan g(x) bahwa keduanya mengikuti relasi big-O dengan order atau pangkat yang sama.

Penjelasan :

Kenyataan bahwa f(x) adalah g(x) kadang-kadang ditulis f(x) = O(g(x)). Bagaimanapun, tanda sama dengan pada notasi tersebut tidak dapat dipresentasikan dengan sebuah persamaan sesungguhnya.

Selanjutnya, notasi tersebut mengambarkan bahwa pertidaksamaan yang diperoleh menghubungkan nilai pada fungsi f dan g untuk bilangan yang cukup besar pada domain fungsi tersebut.

Notasi big-O digunakan pada bidang matematika, khususnya pada ilmu Komputer untuk analisa algoritma. Matematikawan jerman yang memperkenalkan pertama kali notasi big-O pada tahun 1892 pada sebuah buku tentang teori Bilangan. Notasi big-O kadang – kadang disebut juga dengan Simbol Landau.

Ketika f(x) adalah O(g(x)), dan h(x) adalah sebuah fungsi yang mempunyai nilai absolute lebih besar dari pada g(x) untuk bilangan x yang cukup besar, mengikuti definisi diatas maka f(x) adalah O(h(x)). Dengan kata lain, fungsi g(x) pada relasi f(x) adalah O(g(x)) dapat dipresentasikan dengan sebuah fungsi dengan nilai absolute yang lebih besar.

| f(x) | < C |g(x)| jika x > k

Dan jika | h(x) | > | g(x) untuk semua x > k, maka :

| f(x) | < C |h(x)| jika x > k

Oleh karena itu f(x) adalah O(h(x)).

Ketika notasi big-O digunakan, fungsi g pada relasi f(x) adalah O(g(x)) dipilih dari nilai terkecil yang mungkin. Kadang – kadang dari sebuah himpunan fungsi tertentu, misalnya fungsi tersebut pada bentuk xⁿ , dimana n adalah bilangan integer positif.

Contoh 2 :

Tunjukkan bahwa 7 x² adalah O(x³).

Penyelesaian :

Pertidaksamaan 7 x² < x³ dimana x > 7. terlihat bahwa pembagian kedua sisi pertidaksamaan dengan x². oleh karena itu, 7 x² adalah O(x³), dengan mengambil C = 1 dan k = 7 pada definisi notasi big-O.

Contoh 3 :

Pada contoh 2 ditunjukkan bahwa 7 x² adalah O(x³). Apakah juga benar bahwa x³ adalah O(7 x²) ?

Penyelesaiannya :

Untuk menentukan apakah x³ adalah O(7 x²), perlu ditentukan apakah terdapat konstanta C dan k sedemikian sehingga x³ < C (7 x²) dimana x > k. pertidaksamaan tersebut ekuivalen dengan pertidaksamaan x < 7 C, dimana dihasilkan dari pembagian kedua sisi dengan x².

Tidak ada C jika x dibuat untuk sebarang bilangan yang lebih besar. Oleh karena itu x³ bukan O(7 x³).

Polynomial sering digunakan untuk mengestimasi fungsi pertumbuhan. Analisa pertumbuhan pada polynomial untuk setiap waktu, diperlukan hasil yang selalu dapat digunakan untuk mengestimasi pertumbuhan polynomial.

Teorema 2.1

Diberikan f(x) = a_nxⁿ + a_n-1 x^n-1 +…+ a₁ x + a₀, dimana a₀, a₁, …,a_n-1, a_n adalah bilangan real. Maka f(x) adalah O(xⁿ).

Bukti :

Dengan menggunakan pertidaksamaan segitiga, jika x > 1, diperoleh :

| f(x) | = | a_nxⁿ + a_n-1 x^n-1 +…+ a₁ x + a₀ |

< | a_n | xⁿ + | a_n-1 | x^n-1 +…+ | a₁ | x + |a₀ |

= | xⁿ ( |a_n |+ | a_n-1 | / x +…+ | a₁ | / x ^n-1 + |a₀ | / xⁿ )

< x_n ( | a_n| + | a_n-1 | +…+ | a₁ | + |a₀ | ).

Terlihat bahwa

| f(x) | < C xⁿ ,

dimana C ⁼ |a_n | + | a_n-1 | +…+ | a₁ | + |a₀ | untuk x > 1.

Oleh karena itu, f(x) adalah O(xⁿ).

Contoh 4 :

Bagaimana notasi big-O digunakan untuk mengestimasi jumlahan pertama interger positif.

Penyelesaian :

Jika setiap integer pada jumlahan pertama n integer positif tidak melebihi n, mengikuti aturan diatas maka :

1 + 2 + 3 + …+ n < n + n + …+ n = n²

Dari pertidaksamaan tersebut maka 1 + 2 + 3 +… + n adalah O(n²), dengan mengambil C = 1 dan k = 1 pada definisi notasi big-O.

Pada contoh ini domain fungsi big-O relasinya adalah himpunan integer positif.

Contoh 5 :

Dapatkan estimasi big-O untuk fungsi factorial dan logaritma pada fungsi factorial, dimana fungsi factorial f(n) = n! didefinisikan dengan :

n ! = 1 * 2 * 3 …. * n

Dimana n adalah integer positif, dan 0 ! = 1, sebagai contoh :

1 ! = 1

2 ! = 1 . 2 = 2

3 ! = 1. 2 . 3 = 6 dan seterusnya

Penyelesaian :

Sebuah estimasi big-O pada n ! dapat diperoleh dengan catatan bahwa setiap hubungan dalam perkalian tidak melebihi n, sehingga :

n ! = 1 * 2 * 3 …. * n

< n * n * n …. * n

= nⁿ

Pertidaksamaan tersebut menunjukkan bahwa n ! adalah O(nⁿ). dengan mengambil logaritma dari kedua sisi pertidaksamaan terbukti untuk n !, diperoleh:

log n ! < log nⁿ = n log n

secara tidak langsung bahwa log n ! adalah O(nⁿ).

Kombinasi Fungsi Pertumbuhan

Banyak algoritma dibuat pada dua atau lebih sub prosedur. Jumlah langkah yang digunakan oleh komputer untuk menyelesaikan sebuah permasalahan dengan input / masukan tertentu pada sebuah algoritma adalah jumlah setiap langkah yang digunakan oleh sub prosedur tersebut. Untuk mendapatkan estimasi big-O pada jumlah langkah yang dibutuhkan, sangat perlu untuk menemukan estimasi big-O pada jumlah langkah yang digunakan pada setiap sub prosedur dan selanjutnya estimasi tersebut dikombinasikan.

Estimasi big-O pada kombinasi fungsi dapat ditetapkan jika ketelitian yang diambil berbeda estimasi big-O nya untuk digabungkan. Khususnya sangat perlu untuk mengestimasi pertumbuhan pada jumlahan dan perkalian dua fungsi. Misalkan f₁(x) adalah O(g₁(x)) dan f₂(x) adalah O(g₂(x)), dari definisi notasi big-O, disana terdapat konstanta C₁, C₂ , k₁ dan k₂ sedemikian sahingga :

| f₁(x) | < C₁ | g₁(x) |

Ketika x > k₁ dan

| f₂(x) | < C₂ | g₂(x) |

Ketika x > k_2, untuk mengestimasi jumlahan pada f₁(x) dan f₂(x), perhatikan bahwa

| (f₁ + f₂ ) (x) | = | f₁(x) + f₂(x) | :

< | f₁(x) + f₂(x) |, dengan menggunakan pertidaksamaan segitiga, maka :

| a + b | < | a | + | b |.

Ketika x lebih besar dari k₁ dan k_2, dengan mengikuti pertidaksamaan untuk | f₁(x) | dan | f₂(x) | maka :

| f₁(x) | + | f₂(x) | < C₁ | g₁(x) | + C₂ | g₂(x) |

< C₁ | g(x) | + C₂ | g(x) |

= ( C₁ + C₂ ) | g(x) |

= C | g(x) |

Dimana C = C₁ + C₂ dan g(x) = max ( | g₁ (x) | , | g₂ (x) | ).

Ekspresi max (a, b) menunjukkan maksimum atau lebih besar pada a dan b.

Pertidaksamaan tersebut menunjukkan bahwa | (f₁ + f₂ ) (x) | < C | g(x) | dimana x > k, dimana k = max (k₁ + k₂). Hasil tersebut digunakan sebagai teorema sebagai berikut :

Teorema 2.2

Diberikan f₁(x) adalah O(g₁(x)) dan f₂(x) adalah O(g₁(x)), maka ( f₁(x) + f₂(x) ) (x) adalah O(max(g₁(x), g₂(x))). Selanjutnya disebut juga dengan Maximum rule.

Seringkali didapatkan estimasi big-O untuk f₁ dan f₂ pada hubungan tersebut mempunyai fungsi yang sama yaitu g, pada situasi ini, teorema 2.2 dapat digunakan untuk menunjukkan bahwa (f₁ + f₂ ) (x) adalah juga O(g₂(x)), jika max (g(x), g(x)) = g(x). Hasil tersebut ditetapkan sebagai akibat.

Akibat Teorema 2.2

Diberikan f₁(x) adalah O(g(x)) dan f₂(x) adalah O(g(x)), maka ( f₁+ f₂) (x) adalah O(g(x)).

| f₁(x) | + | f₂(x) | < C₁ | g(x) | + C₂ | g(x) |

< C₁ | g(x) | + C₂ | g(x) |

= ( C₁ + C₂ ) | g(x) |

= C | g(x) |

Dimana C = C₁ + C₂ dan g(x) = max ( | g (x) | , | g (x) | ).

Maka didapatkan O(g(x)).

Dengan cara yang sama estimasi big-O dapat diperoleh dengan perkalian fungsi f₁ dan f_2. ketika x lebih besar daripada max (k₁ , k₂), maka :

| (f₁ f₂) (x) | = | f₁(x) | . | f₂(x) |

< C₁ | g₁(x) | . C₂ | g₂ (x) |

< C₁ C₂ | (g₁ g₂ ) (x) |

< C | (g₁ g₂ ) (x) |

Dimana C = C₁ C₂.

Dari pertidaksamaan tersebut, dengan mengikuti definisi maka f₁(x) f₂(x) adalah O(g₁ g₂), sehingga terdapat konstanta C dan k, yaitu C = C₁ C₂ dan k = max(k₁ , k₂),.

Karena | ( f₁ f₂ ) (x) | < C | ( g₁ g₂ ) (x) | , dimana x > k. Hasil tersebut ditetapkan sebagai teorema berikut :

Teorema 2.3

Diberikan f₁(x) adalah O(g₁(x)) dan f₂(x) adalah O(g₂(x)). Maka (f₁ f₂) (x) adalah O(g₁(x) g₂(x)).

Tujuan menggunakan notasi big-O pada fungsi estimasi adalah untuk memilih sebuah fungsi g(x) pada pertumbuhan relative terendah dengan f(x) adalah O(g(x)).

Contoh 6 :

Dapatkan estimasi big-O untuk f(n) = 3 n log(n !) + (n² + 3 ) log n, dimana n adalah bilnagan integer positif.

Penyelesaian :

Pertama, perkalian 3 n log(n !) akan diestimasikan. Dari contoh 5 diketahui bahwa log(n!) adalah O(n log n).

Menggunakan estimasi tersaebut dan 3n adalah O(n).

Teorema 2.3 memberikan estimasi bahwa 3 n log(n) adalah O(n² log n).

Selanjutnya, perkalian (n² + 3 ) log n akan diestimasikan. Untuk ( n² + 3 ) < 2 n^2, , maka n > 2, sehingga (n² + 3 ) adalah O (n² ).

Berdasarkan teorema 2.3, maka ( n² + 3 ) log n adalah O(n² log n).

Dengan menggunakan teorema 2.2 maka menggabungkan dua estimasi big-O untuk perkalian terlihat bahwa f(n) = 3 n log(n !) + (n² + 3) log n adalah O(n² log n).

Contoh 7 :

Dapatkan estimasi big-O untuk f(x) = (x + 1) log(x² + 1 ) + 3 x²

Penyelesaian :

Pertama, estimasi big-O untuk (x + 1) log(x² + 1 ) akan diperoleh. Catatan (x +1) adalah O(x). Selanjutnya, x² + 1 < 2 x² ketika x > 1.

Sehingga, log(x² + 1) < log(2 x²) = log 2 + log x² = log 2 + 2 log x < 3 log x, jika x> 2.

Hal ini terlihat bahwa log(x² + 1) adalah O(log x).

Dari teorema 2.3 bahwa (x + 1) log(x² + 1) adalah O(x log x).

Untuk 3 x² adalah O (x² ), teorema 2.2 menunjukkan bahwa f(x) adalah max(O(x log x, x²)).

Padahal x log x < x², untuk x > 1, sehingga f(x) adalah O (x² ).