Title Soal WA1 ✅

1. [6 + 4 + 6 + 9 + 5 = 30 poin] Tentukan nilai kebenaran dari pernyataan berikut dan berikan alasannya! a. n (disarankan untuk tidak menggunakan limit) 100 = O 2 n 2 ( ) b. Jika f(n) = O(g(n)), maka 2 . f(n) = O(2 g(n) ) c. Jika f(n) = o(g(n)) dan n → ∞ sehingga g(n) → ∞ maka 2 f(n) = o(2 g(n) ) d. ln (n) + ln n 2 ( ) + ln n 3 ( ) + ... + ln(n n ) = θ(ln n 2 ( !) ) e. n! ∈ ω(n n ) 2. [2 + 3 + 10 + 6 + 6 + 3 = 30 poin] Perhatikan kode dibawah ini! def what(N): result = 0 for i in range(1, 1000): temp = 0 while temp < 1000: if temp == N: result += 1 temp += i return result a. Jelaskan secara singkat apa yang dilakukan fungsi ini terhadap bilangan bulat positif N kurang dari 1000 berdasarkan analisis Anda! b. Apakah benar bahwa algoritma tersebut tidak selalu bekerja semestinya untuk bilangan bulat besar lebih dari sama dengan 1000? Jika benar, lakukan perbaikan pada algoritma tersebut dengan syarat hanya mengubah 2 baris kode saja. Tuliskan ulang keseluruhan fungsi what yang telah Anda perbaiki dan berikan penanda (seperti kotak atau highlight) pada baris yang diubah! c. Definisikan loop invariant untuk membuktikan kebenaran dari kode tersebut, lalu buktikan secara formal dengan properti (i) inisialisasi, (ii) maintenance, dan (iii) termination, bahwa algoritma yang telah Anda desain ulang bekerja dengan benar untuk sembarang nilai N bilangan positif. (Petunjuk: perhatikan bahwa Anda perlu melakukan 2 kali pembuktian loop invariant) d. Analisislah running time T(n) dari algoritma tersebut kemudian buatlah ke dalam notasi Big θ, dengan N adalah sebuah integer input! Untuk memudahkan, Anda dapat menuliskan time complexity dari setiap baris. Asumsikan semua operasi assignment (=), perbandingan, return, dan aritmatika berjalan secara konstan (c). Jangan lupa untuk menghitung semua operasi yang terdapat dalam satu baris. e. Desainlah sebuah algoritma yang lebih efisien dari fungsi diatas! Kumpulkan solusi kalian melalui Judgels. Poin yang kamu dapatkan di soal ini bergantung pada poin yang didapatkan di Judgels!