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

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

Както се разбрахме, оставям ви тук още няколко дребни задачи, върху които да помислите накратко когато можете. Следващото упражнение ще започнем с тях.

Вярно ли е, че за всяка функция f е изпълнено:

• f(n) = Θ(f(n/2))
  
• f(n) = Θ(f(n+1))
  
• lg(f(n)) = o(f(n))? Ако това свойство не е винаги вярно, посочете множество функции, за които е изпълнено.

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