contoh kasus komputasii Modern

Contoh lain penerapan komputasi modern adalah di dibidang kesehatan, khususnya website rumah sakit. Disini, saya menggunakan contoh website Rumah Sakit Pusat Pertamina

(http://www.pertaminahospital.com/).

Penerapan komputasi modern khususnya cloud computing dapat dilihat dari pencarian jadwal dokter dan juga pasien dapat membooking jadwal (melakukan pendaftaran) secara online.

Berikut adalah tampilan awal website :

Untuk pencarian (search) dapat dilakukan dengan memilih pada menu utama yaitu Jadwal dokter atau pada sidebar yaitu Praktek Dokter. Output yang ditampilkan sama. Berikut ini adalah pencarian jadwal dokter menggunakan menu utama.

Pertama-tama, pilih jadwal dokter. Kemudian, pilih spesialisasi maka akan muncul nama dokter berdasarkan spesialisasinya. Lalu, pasien cukup memilih nama dokternya, informasi mengenai dokter tersebut lengkap dengan jadwalnya akan tampil seperti gambar berikut :

 

Untuk booking jadwal, fasilitas ini sebenarnya hanya berlaku apabila pasien sudah mendaftar sebelumnya dan memperoleh kartu pasien. Pasien cukup mengisi data pada formulir yang tersedia seperti nama, nomor kartu, tempat tanggal lahir, alamat, telepon, email, via contact, pilih poliklinik yang diinginkan, pilih dokter, formulir seperti pada gambar berikut :

Komentar :

Menurut saya, website ini sudah cukup baik. Pasien dapat dengan mudah memperoleh informasi tentang dokter dan pasien dapat mencari dokter berdasarkan spesialisasi, sehingga mempercepat pencarian sesuai dengan kebutuhan pasien. Satu hal yang menjadi perbedaan situs Rumah Sakit Pusat Pertamina dengan situs rumah sakit lainnya adalah, adanya layanan booking jadwal (pendaftaran secara online). Hal ini sangat memberi kemudahan pada pasien apalagi untuk pasien yang bertempat tinggal cukup jauh dari rumah sakit. Walaupun saya belum pernah menggunakan fasilitas ini, salah seorang teman saya yang selalu memeriksakan diri di rumah sakait tersebut mengatakan bahwa pendaftaran online jauh lebih praktis. Dan karena pasien sudah mendafar terlebih dahulu melalui pendaftaran online, saat sampai dirumah sakit pelayanannya akan lebih cepat dilaksanakan.Namun, ada kekurangan pada website ini terutama dalam hal pencarian jadwal dokter. Karena, pasien harus mencari jadwal berdasarkan nama dokter sedangkan tidak semua pasien mengenal dokter tertentu apalagi jika pasien hanya ingin mengetahui jadwal dokter umum atau hanya ingin mengetahui siapa saja dokter yang bertugas pada hari tertentu. Pencarian berdasarkan nama dokter memang dapat mempermudah untuk beberapa hal. Tapi, alangkah lebih baik jika pencarian hanya didasarkan pada spesialisasi sehingga, output yang dikeluarkan adalah nama-nama dokter sesuai spesialisai beserta jadwalnya.

https://3anapoe3.wordpress.com/2013/05/01/contoh-lain-penerapan-komputasi-modern/

Kompleksitas

Kompleksitas komputasi adalah cabang dari teori komputasi dalam ilmu komputer yang berfokus pada mengklasifikasikan masalah komputasi sesuai dengan kesulitan inheren mereka. Dalam konteks ini, sebuah masalah komputasi dipahami sebagai tugas yang pada prinsipnya setuju untuk menjadi dipecahkan oleh komputer. Informal, sebuah masalah komputasi terdiri dari contoh-contoh masalah dan solusi untuk masalah ini contoh. Sebagai contoh, primality pengujian adalah masalah menentukan apakah nomor yang diberikan perdana atau tidak. Contoh-contoh masalah ini adalah bilangan asli, dan solusi untuk sebuah contoh adalah ya atau tidak didasarkan pada apakah nomor perdana atau tidak.

Masalah ini dianggap sebagai secara inheren sulit jika memecahkan masalah yang memerlukan sejumlah besar sumber daya, tergantung pada algoritma yang digunakan untuk memecahkan itu. Teori ini formalizes intuisi, dengan memperkenalkan matematika model komputasi untuk mempelajari masalah ini dan kuantitatif jumlah sumber daya yang dibutuhkan untuk memecahkan mereka, seperti waktu dan penyimpanan. Ukuran kompleksitas lain juga digunakan, seperti jumlah komunikasi (digunakan dalam kompleksitas komunikasi), jumlah gerbang dalam rangkaian (digunakan dalam rangkaian kompleksitas) dan jumlah prosesor (digunakan dalam komputasi paralel). Secara khusus, teori kompleksitas komputasi menentukan batas-batas praktis tentang apa yang komputer bisa dan tidak bisa lakukan.

Bidang-bidang terkait erat dalam ilmu komputer teoritis analisis algoritma dan teori computability. Perbedaan utama antara teori kompleksitas komputasi dan analisis algoritma adalah bahwa yang terakhir ditujukan untuk menganalisis jumlah sumber daya yang dibutuhkan oleh algoritma tertentu untuk memecahkan masalah, sedangkan yang pertama mengajukan pertanyaan yang lebih umum tentang semua kemungkinan algoritma yang dapat digunakan untuk memecahkan masalah yang sama. Lebih tepatnya, hal ini mencoba untuk mengklasifikasikan masalah yang dapat atau tidak dapat diselesaikan dengan tepat sumber daya terbatas. Pada gilirannya, memaksakan pembatasan pada sumber daya yang tersedia adalah apa yang membedakan kompleksitas komputasi dari computability teori: teori yang terakhir bertanya apa jenis masalah dapat diselesaikan pada prinsipnya algorithmically.

Pemecahan Masalah Kompleksitas (Menggunakan teori Big O)

Komputasi modern dirancang untuk menangani masalah yang kompleks, sehingga diterapkan pada komputer. Dengan menggunakan teori Big O, maka komputasi modern dapat melakukan perhitungan untuk memecahkan masalah kompleksitas yang kerap dihadapi.

Apa itu teori Big O?

Notasi  Big O merupakan suatu notasi matema tika untuk menjelaskan batas atas dari  magnitude suatu fungsi dalam fungsi yang lebih sederhana. Dalam dunia ilmu komputer, notasi ini sering digunakan dalam analisis kompleksitas algoritma. Notasi  Big O pertama kali diperkenalkan pakar teori bilangan Jerman, Paul Bachman tahun 1894, pada bukunya yang berjudul  Analytische Zahlentheorie edisi kedua. Notasi tersebut kemudian dipopuler kan oleh pakar teori bilangan Jerman lainnya, Edmund Landau, dan oleh karena  itu, terkadang disebut sebagai symbol Landau.

Notasi  Big O sangat berguna saat menganalis is efisiensi suatu algoritma. Sebagai contoh, waktu (atau jumlah langkah) yang diperlukan oleh suatu algoritma untuk menyelesaikan tugas dengan ukuran n adalah T( n) = 4 n -2 n+2. Untuk n yang besar, hasil perhitungan  n² menjadi dominan, sehingga  perhitungan yang lain dapat diabaikan (misalnya saat  n=500, 4n² 1000 kali lebih besar dari 2 n, sehingga mengabaikan 2n+2 tidak akan membawa efek yang besar pada tujuan utama pada umumnya). Kemudian koefisien pada polinomial pun dapat dihilangkan dengan alasan yang sama, sehingga dengan notasi big O, dapat disimpulkan:  T(n) E O(n²) bahwa algoritma di atas memiliki kompleksitas waktu dengan orde  O(n²).

Untuk membandingkan kompleksitas algoritma yang satu dengan yang lain, dapat digunakan tabel jenis kompleksitas di bawah, yang diurutkan berdasarkan kompleksitas yang paling baik ke yang paling buruk.

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 :

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

Penyelesaian :

Jika 0 < x2 + 2 x + 1 < x2 + 2 x2 + x2 = 4 x2 dimana x > 1, mengikuti f(x) adalah O(x2) 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 < x2. akibatnya jika x > 2, terlihat bahwa :

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

Dari definisi didapat C = 3 dan k = 2.

Pengamatan pada relasi f(x) adalah O(x2), x2 dapat diganti dengan sebarang fungsi yang lain dengan nilai yang lebih besar dari x2, misalnya f(x) adalah O(x3), f(x) adalah O(x2+2x+7) dan seterusnya. Hal ini juga benar bahwa x2 adalah O(x2+2x+1), jika x2 < x2 + 2x +1 dimana x > 1. Dari contoh tersebut diperoleh dua fungsi, f(x) = x2 + 2 x + 1 dan g(x) = x2, sedemikian sehingga f(x) adalah O(g(x)) dan g(x) adalah O(f(x)).

Pernyataan terakhir dari pertidaksamaan x2 < x2 + 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 xn , dimana n adalah bilangan integer positif.

Contoh Masalah :

Sebuah masalah komputasi dapat dilihat sebagai sebuah koleksi yang tak terbatas kasus bersama-sama dengan solusi untuk setiap contoh. Input string untuk sebuah masalah komputasi disebut sebagai contoh masalah, dan tidak boleh bingung dengan masalah itu sendiri. Dalam teori kompleksitas komputasi, masalah mengacu pada pertanyaan abstrak yang harus dipecahkan. Sebaliknya, sebuah contoh dari masalah ini adalah ucapan yang agak konkret, yang dapat digunakan sebagai masukan untuk masalah keputusan. Sebagai contoh, perhatikan masalah primality pengujian. contoh adalah nomor dan solusinya adalah "ya" jika nomor perdana dan "tidak" sebaliknya. Bergantian, yang contoh adalah input tertentu untuk masalah, dan solusinya adalah output sesuai dengan input yang diberikan.

Untuk lebih menyoroti perbedaan antara masalah dan sebuah contoh, pertimbangkan contoh berikut versi keputusan dari pedagang keliling masalah: Apakah ada rute dengan panjang maksimal 2000 kilometer melewati semua di Jerman 15 kota terbesar? Jawaban untuk masalah khusus ini misalnya tidak banyak digunakan untuk menyelesaikan contoh-contoh lain dari masalah, seperti meminta untuk pulang-pergi melalui semua pemandangan di Milan yang jumlah paling banyak panjangnya 10km. Untuk alasan ini, teori kompleksitas komputasi alamat masalah dan bukan masalah tertentu.

contoh kasus komputasi modern

Contoh lain penerapan komputasi modern adalah di dibidang kesehatan, khususnya website rumah sakit. Disini, saya menggunakan contoh website Rumah Sakit Pusat Pertamina

(http://www.pertaminahospital.com/).

Penerapan komputasi modern khususnya cloud computing dapat dilihat dari pencarian jadwal dokter dan juga pasien dapat membooking jadwal (melakukan pendaftaran) secara online.

Berikut adalah tampilan awal website :

Untuk pencarian (search) dapat dilakukan dengan memilih pada menu utama yaitu Jadwal dokter atau pada sidebar yaitu Praktek Dokter. Output yang ditampilkan sama. Berikut ini adalah pencarian jadwal dokter menggunakan menu utama.

Pertama-tama, pilih jadwal dokter. Kemudian, pilih spesialisasi maka akan muncul nama dokter berdasarkan spesialisasinya. Lalu, pasien cukup memilih nama dokternya, informasi mengenai dokter tersebut lengkap dengan jadwalnya akan tampil seperti gambar berikut :

 

Untuk booking jadwal, fasilitas ini sebenarnya hanya berlaku apabila pasien sudah mendaftar sebelumnya dan memperoleh kartu pasien. Pasien cukup mengisi data pada formulir yang tersedia seperti nama, nomor kartu, tempat tanggal lahir, alamat, telepon, email, via contact, pilih poliklinik yang diinginkan, pilih dokter, formulir seperti pada gambar berikut :

Komentar :

Menurut saya, website ini sudah cukup baik. Pasien dapat dengan mudah memperoleh informasi tentang dokter dan pasien dapat mencari dokter berdasarkan spesialisasi, sehingga mempercepat pencarian sesuai dengan kebutuhan pasien. Satu hal yang menjadi perbedaan situs Rumah Sakit Pusat Pertamina dengan situs rumah sakit lainnya adalah, adanya layanan booking jadwal (pendaftaran secara online). Hal ini sangat memberi kemudahan pada pasien apalagi untuk pasien yang bertempat tinggal cukup jauh dari rumah sakit. Walaupun saya belum pernah menggunakan fasilitas ini, salah seorang teman saya yang selalu memeriksakan diri di rumah sakait tersebut mengatakan bahwa pendaftaran online jauh lebih praktis. Dan karena pasien sudah mendafar terlebih dahulu melalui pendaftaran online, saat sampai dirumah sakit pelayanannya akan lebih cepat dilaksanakan.Namun, ada kekurangan pada website ini terutama dalam hal pencarian jadwal dokter. Karena, pasien harus mencari jadwal berdasarkan nama dokter sedangkan tidak semua pasien mengenal dokter tertentu apalagi jika pasien hanya ingin mengetahui jadwal dokter umum atau hanya ingin mengetahui siapa saja dokter yang bertugas pada hari tertentu. Pencarian berdasarkan nama dokter memang dapat mempermudah untuk beberapa hal. Tapi, alangkah lebih baik jika pencarian hanya didasarkan pada spesialisasi sehingga, output yang dikeluarkan adalah nama-nama dokter sesuai spesialisai beserta jadwalnya.

https://3anapoe3.wordpress.com/2013/05/01/contoh-lain-penerapan-komputasi-modern/

Kompleksitas

Kompleksitas komputasi adalah cabang dari teori komputasi dalam ilmu komputer yang berfokus pada mengklasifikasikan masalah komputasi sesuai dengan kesulitan inheren mereka. Dalam konteks ini, sebuah masalah komputasi dipahami sebagai tugas yang pada prinsipnya setuju untuk menjadi dipecahkan oleh komputer. Informal, sebuah masalah komputasi terdiri dari contoh-contoh masalah dan solusi untuk masalah ini contoh. Sebagai contoh, primality pengujian adalah masalah menentukan apakah nomor yang diberikan perdana atau tidak. Contoh-contoh masalah ini adalah bilangan asli, dan solusi untuk sebuah contoh adalah ya atau tidak didasarkan pada apakah nomor perdana atau tidak.

Masalah ini dianggap sebagai secara inheren sulit jika memecahkan masalah yang memerlukan sejumlah besar sumber daya, tergantung pada algoritma yang digunakan untuk memecahkan itu. Teori ini formalizes intuisi, dengan memperkenalkan matematika model komputasi untuk mempelajari masalah ini dan kuantitatif jumlah sumber daya yang dibutuhkan untuk memecahkan mereka, seperti waktu dan penyimpanan. Ukuran kompleksitas lain juga digunakan, seperti jumlah komunikasi (digunakan dalam kompleksitas komunikasi), jumlah gerbang dalam rangkaian (digunakan dalam rangkaian kompleksitas) dan jumlah prosesor (digunakan dalam komputasi paralel). Secara khusus, teori kompleksitas komputasi menentukan batas-batas praktis tentang apa yang komputer bisa dan tidak bisa lakukan.

Bidang-bidang terkait erat dalam ilmu komputer teoritis analisis algoritma dan teori computability. Perbedaan utama antara teori kompleksitas komputasi dan analisis algoritma adalah bahwa yang terakhir ditujukan untuk menganalisis jumlah sumber daya yang dibutuhkan oleh algoritma tertentu untuk memecahkan masalah, sedangkan yang pertama mengajukan pertanyaan yang lebih umum tentang semua kemungkinan algoritma yang dapat digunakan untuk memecahkan masalah yang sama. Lebih tepatnya, hal ini mencoba untuk mengklasifikasikan masalah yang dapat atau tidak dapat diselesaikan dengan tepat sumber daya terbatas. Pada gilirannya, memaksakan pembatasan pada sumber daya yang tersedia adalah apa yang membedakan kompleksitas komputasi dari computability teori: teori yang terakhir bertanya apa jenis masalah dapat diselesaikan pada prinsipnya algorithmically.

Pemecahan Masalah Kompleksitas (Menggunakan teori Big O)

Komputasi modern dirancang untuk menangani masalah yang kompleks, sehingga diterapkan pada komputer. Dengan menggunakan teori Big O, maka komputasi modern dapat melakukan perhitungan untuk memecahkan masalah kompleksitas yang kerap dihadapi.

Apa itu teori Big O?

Notasi  Big O merupakan suatu notasi matema tika untuk menjelaskan batas atas dari  magnitude suatu fungsi dalam fungsi yang lebih sederhana. Dalam dunia ilmu komputer, notasi ini sering digunakan dalam analisis kompleksitas algoritma. Notasi  Big O pertama kali diperkenalkan pakar teori bilangan Jerman, Paul Bachman tahun 1894, pada bukunya yang berjudul  Analytische Zahlentheorie edisi kedua. Notasi tersebut kemudian dipopuler kan oleh pakar teori bilangan Jerman lainnya, Edmund Landau, dan oleh karena  itu, terkadang disebut sebagai symbol Landau.

Notasi  Big O sangat berguna saat menganalis is efisiensi suatu algoritma. Sebagai contoh, waktu (atau jumlah langkah) yang diperlukan oleh suatu algoritma untuk menyelesaikan tugas dengan ukuran n adalah T( n) = 4 n -2 n+2. Untuk n yang besar, hasil perhitungan  n² menjadi dominan, sehingga  perhitungan yang lain dapat diabaikan (misalnya saat  n=500, 4n² 1000 kali lebih besar dari 2 n, sehingga mengabaikan 2n+2 tidak akan membawa efek yang besar pada tujuan utama pada umumnya). Kemudian koefisien pada polinomial pun dapat dihilangkan dengan alasan yang sama, sehingga dengan notasi big O, dapat disimpulkan:  T(n) E O(n²) bahwa algoritma di atas memiliki kompleksitas waktu dengan orde  O(n²).

Untuk membandingkan kompleksitas algoritma yang satu dengan yang lain, dapat digunakan tabel jenis kompleksitas di bawah, yang diurutkan berdasarkan kompleksitas yang paling baik ke yang paling buruk.

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 :

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

Penyelesaian :

Jika 0 < x2 + 2 x + 1 < x2 + 2 x2 + x2 = 4 x2 dimana x > 1, mengikuti f(x) adalah O(x2) 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 < x2. akibatnya jika x > 2, terlihat bahwa :

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

Dari definisi didapat C = 3 dan k = 2.

Pengamatan pada relasi f(x) adalah O(x2), x2 dapat diganti dengan sebarang fungsi yang lain dengan nilai yang lebih besar dari x2, misalnya f(x) adalah O(x3), f(x) adalah O(x2+2x+7) dan seterusnya. Hal ini juga benar bahwa x2 adalah O(x2+2x+1), jika x2 < x2 + 2x +1 dimana x > 1. Dari contoh tersebut diperoleh dua fungsi, f(x) = x2 + 2 x + 1 dan g(x) = x2, sedemikian sehingga f(x) adalah O(g(x)) dan g(x) adalah O(f(x)).

Pernyataan terakhir dari pertidaksamaan x2 < x2 + 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 xn , dimana n adalah bilangan integer positif.

Contoh Masalah :

Sebuah masalah komputasi dapat dilihat sebagai sebuah koleksi yang tak terbatas kasus bersama-sama dengan solusi untuk setiap contoh. Input string untuk sebuah masalah komputasi disebut sebagai contoh masalah, dan tidak boleh bingung dengan masalah itu sendiri. Dalam teori kompleksitas komputasi, masalah mengacu pada pertanyaan abstrak yang harus dipecahkan. Sebaliknya, sebuah contoh dari masalah ini adalah ucapan yang agak konkret, yang dapat digunakan sebagai masukan untuk masalah keputusan. Sebagai contoh, perhatikan masalah primality pengujian. contoh adalah nomor dan solusinya adalah "ya" jika nomor perdana dan "tidak" sebaliknya. Bergantian, yang contoh adalah input tertentu untuk masalah, dan solusinya adalah output sesuai dengan input yang diberikan.

Untuk lebih menyoroti perbedaan antara masalah dan sebuah contoh, pertimbangkan contoh berikut versi keputusan dari pedagang keliling masalah: Apakah ada rute dengan panjang maksimal 2000 kilometer melewati semua di Jerman 15 kota terbesar? Jawaban untuk masalah khusus ini misalnya tidak banyak digunakan untuk menyelesaikan contoh-contoh lain dari masalah, seperti meminta untuk pulang-pergi melalui semua pemandangan di Milan yang jumlah paling banyak panjangnya 10km. Untuk alasan ini, teori kompleksitas komputasi alamat masalah dan bukan masalah tertentu.