Cevaplı Algoritmalar ve karmaşıklık çalışma kâğıdı

Zaten sıralı bir dizide eklemeli sıralamanın en iyi durum zaman karmaşıklığı nedir?

1. AO(n)
2. BO(n²)
3. CO(n log n)
4. DO(1)

f(n) = Θ(g(n)) ne anlama gelir?

1. Af, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
2. Bf, g'den kesinlikle daha yavaş büyür
3. Cf her n için her zaman g'den küçüktür, yani g onu yukarıdan sınırlar ama aşağıdan asla sınırlamaz
4. Df, g'den kesinlikle daha hızlı büyür

Özyineleme nedir?

1. AHiç bitmeyen bir döngü
2. BBir veri yapısı türü
3. CKendisini daha küçük girdilerle çağıran bir fonksiyon
4. DBir sıralama yöntemi

Basit özyinelemeli faktöriyel fonksiyonu fact(n) = n × fact(n − 1) ne kadar yığın (stack) alanı kullanır?

1. AO(1)
2. BO(n)
3. CO(n²)
4. DO(log n)

Saf özyinelemeli Fibonacci'nin (fib(n) = fib(n−1) + fib(n−2)) zaman karmaşıklığı nedir?

1. ALogaritmik
2. BÜstel
3. CDoğrusal
4. DSabit

O(log n)'de olduğu gibi, Büyük O'da logaritmanın tabanı neden genellikle yazılmaz?

1. ATaban yalnızca küçük n için önemlidir
2. BBilgisayar bilimindeki tüm logaritmaların tabanı 10'dur, bu yüzden zımnen bellidir
3. CFarklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
4. DLogaritmalar her zaman tamsayılara yuvarlanır

İkili arama tek yönlü bağlı listede neden O(log n) zaman vermez?

1. ABağlı liste düğümlerindeki karşılaştırmalar daha yavaştır
2. BBağlı listeler sıralanamaz
3. Cİkili arama en az iki kat bellek gerektirir
4. DDoğrudan indeks erişimi olmadığından ortadaki elemana ulaşmak O(n) adım alır

Karatsuba çarpması T(n) = 3T(n/2) + O(n) yinelemesini sağlar. Bunun çözümü nedir?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), yaklaşık n^1,585