Дизайн и анализ на алгоритми, КН2, пролет 2019

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

Както се разбрахме по време на редовното ни упражнение, следващото ни упражнение ще бъде на 6 март (сряда), от 16 до 18ч в зала 401.
Ще продължим с материала за асимптотичните нотации и сравнения на функции, за да не изоставаме твърде много от лекциите.

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

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).