Дизайн и анализ на алгоритми, КН2, летен семестър 2017/2018

Здравейте, колеги,

Вчера на упражнението ви бях казал, че исках да ви дам няколко задачки "за вкъщи", но не ги бях намерил - е, пиша ви ги тук с надеждата да ги помислите когато имате време, пък ще започнем с тях следващото упражнение:

1. Докажете, че ако f₁ = Θ(f₂) и g₁ = Θ(g₂), то f₁.g₁ = Θ(f₂.g₂)
2. Докажете или опровергайте, че ако f₁ = Θ(f₂) и g₁ = Θ(g₂), то f₁^g₁ = Θ(f₂^g₂)
3. Докажете или опровергайте, че ако f = O(g) и f != Θ(g), то f = o(g).

Под горното обозначение f.g стандартно имаме предвид функцията h(n)=f(n).g(n); под f^g имаме предвид функцията h(n) = f(n) на степен g(n).

Поздрави,
Андрей

Edit: поправени сбъркани условията на 1. и 2.