Bir algoritma problemi

Question

Bir algoritma girdi olarak aldığı $n$ adet sayıdan oluşturulan tekrarsız ve elemanları birbirinden farklı her bir ikili üzerine $X$ işlemini uygulamaktadır. $X$ işleminin de $[1…log_{2} n)$ aralığındaki $2$’nin kuvveti olan tamsayılardan her biri için bir kez $Y$ işlemi yaptığı bilinmektedir. Buna göre bu algoritma toplamda kaç tane $Y$ işlemi yapar?

$A) n^2 \log_{2}(2^n)$

$B) [(n^2 + n)/2][1 + log_{2} n]$

$C)[(n^2 + n)/2]\log_{2} n$

$D) [n . (n − 1)/2]\log_{2}(\log_{2} n)$

$E) [n . (n − 1)/2]\log_{2}(2^n)$

$cevap:D$

soruyu çözdüm fakat bir nevi cevaplardan gittiğim için içime sinmedi.

Şöyle ki dizi $n$ elemanlı olduğundan ötürü $C(n,2)$ tane ikili olacak ve $X$ işlemi olacak.

Ve bu sadece E ve D'de var.Daha sonra $\log_{2}2^n = n$ olacağından bu cevap da elenir ve geriye

$D$ kalır.Ben böyle yaptım fakat istediğim cevabın nereden $D$ olduğu.Birisi açıklayabilirse çok iyi olur.

Comments

$X$ islemi kac kere gerceklesir: $C(n,2)$.

Pozitif bir $N$'den kucuk kac tane ikinin kuvveti vardir? $\lfloor \log_2N\rfloor$. Senin sorundaki $N=\log_2 n$.

$X$'teki her islem icin $\lfloor \log_2(\log_2n)\rfloor$ tane $Y$ islemi yapiliyor. 

Dolayisiyla bu ikisini carparsin.

$\lfloor \log_2(\log_2n)\rfloor= \log_2(\log_2n)+O(1)$ oldugundan galiba soru soranlar bunu ihmal etmis.

---

Hocam bilgisizliğimi mazur görün.Bir yeri anlayamadım:

$O(1)$ manası nedir?

---

https://tr.wikipedia.org/wiki/Büyük_O_gösterimi

Algoritmacilar genelde bunu kullanillar.

$g$'in $O(f)$ olmasi belirli bir sureden sonra bir M sabiti icin |g|<M|f| olmasi.

Mesela $\sin$ ya da $\cos$ da $O(1)$ olur.

---

Teşekkürler.